Java | Easy | Prefix + Suffix Arrays
\nclass Solution {\n    public int sumOfBeauties(int[] arr) {\n         int n = arr.length;\n         int left[] = new int[n]; //pre-calculate minimum\n        
```\nclass Solution {\n    public int sumOfBeauties(int[] arr) {\n         int n = arr.length;\n         int left[] = new int[n]; //pre-calculate minimum\n         int right[] = new int[n];//pre-calculate maximum\n        \n         left[0] = arr[0];\n         for(int i = 1 ; i < n ; i++){\n              left[i] = Math.max(left[i - 1],arr[i]);\n         }\n        \n         right[n - 1] = arr[n - 1];\n         for(int i = n - 2 ; i >= 0 ; i--){\n              right[i] = Math.min(right[i + 1],arr[i]);\n         }\n        \n         int beauty = 0;\n         for(int i = 1 ; i < n - 1; i++){\n             //According to the question, calculate beauty for every element.\n             if(arr[i] > left[i - 1] && arr[i] < right[i + 1]){\n                 beauty += 2;\n             }\n             else if(arr[i] > arr[i - 1] && arr[i] < arr[i + 1]){\n                 beauty += 1;\n             }\n         }\n        return beauty;\n    } \n}\n```
['Array', 'Suffix Array']