C++ || 2 Approach || Segment Tree OR Pre Compute
2 Approaches.\n Approach 1: Just simply pre-compute the prefix maximum and suffix minimum.\n Approach 2: Using Segment Tree. Specifically merge sort segment tre
**2 Approaches.**\n* Approach 1: Just simply pre-compute the prefix maximum and suffix minimum.\n* Approach 2: Using Segment Tree. Specifically merge sort segment tree\n\n**CODE: APPROACH 1:**\n```\nclass Solution {\npublic:\n    int sumOfBeauties(vector<int>& nums) {\n        int n= nums.size();\n        vector<int> prefix(n); // prefix[i] represent max from [0, i]\n        vector<int> suffix(n); // suffix[i] represent min from [i, n-1]\n        \n        int maxi= INT_MIN;\n        for(int i=0; i<n; i++){\n            maxi= max(maxi, nums[i]);\n            prefix[i]= maxi;\n        }\n        int mini= INT_MAX;\n        for(int i=n-1; i>=0; i--){\n            mini= min(mini, nums[i]);\n            suffix[i]= mini;\n        }\n        \n        int ans=0;\n        for(int i=1; i<n-1; i++){\n            if(prefix[i-1]<nums[i] && nums[i]<suffix[i+1]){ ans+=2; }\n            else if(nums[i-1]<nums[i] && nums[i]<nums[i+1]){ ans+=1; }\n        }\n        return ans;\n    }\n};\n```\nTime Complexity: O(N) || Space Complexity: O(2*N)\n\n**CODE: APPROACH 2:**\n```\nvector<vector<int>> seg;\n\nvoid build(int si, int ss, int se, vector<int>& nums){\n    if(ss==se){\n        seg[si].push_back(nums[ss]);\n        return;\n    }\n    int mid= ss+ (se-ss)/2;\n    build(2*si+1, ss, mid, nums); // build left half recursively\n    build(2*si+2, mid+1, se, nums); // build right half recursively\n    \n    // Now 2 sorted half are seg[2*si+1] and seg[2*si+2]. So, we need to merge them to make seg[si]\n    int i=0; int j=0; int left=2*si+1; int right= 2*si+2;\n    while(i<seg[left].size() && j<seg[right].size()){\n        if(seg[left][i]<seg[right][j]){\n            seg[si].push_back(seg[left][i]);\n            i++;\n        }\n        else{\n            seg[si].push_back(seg[right][j]);\n            j++;\n        }\n    }\n    while(i<seg[left].size()){\n        seg[si].push_back(seg[left][i]);\n        i++;\n    }\n    while(j<seg[right].size()){\n        seg[si].push_back(seg[right][j]);\n        j++;\n    }\n    // seg[si] is ready\n    return;\n}\n\nint binSearch1(vector<int>& vec, int val){ // max index that is smaller than val\n    int low= 0; int high= vec.size()-1; int potCand=-1;\n    while(low<=high){\n        int mid= low+ (high-low)/2;\n        \n        if(vec[mid]<val){\n            potCand=mid;\n            low= mid+1;\n        }\n        else if(vec[mid]>=val){\n            high= mid-1;\n        }\n    }\n    return (potCand==-1) ? 0 : potCand-0+1;\n}\nint binSearch2(vector<int>& vec, int val){ // min index that is larger than val\n    int low= 0; int high= vec.size()-1; int potCand=-1;\n    while(low<=high){\n        int mid= low+ (high-low)/2;\n        \n        if(vec[mid]>val){\n            potCand=mid; //cout<<potCand<<endl;\n            high=mid-1;\n        }\n        else if(vec[mid]<=val){\n            low= mid+1;\n        }\n    }\n    return (potCand==-1) ? 0 : (vec.size()-1-potCand+1);\n}\n\nint query(int si, int ss, int se, int qs, int qe, int val, int type){ \n    // Type 1: --> find number of ele in [qs-qe] that are <val\n    // Type 2: --> find number of ele in [qs-qe] that are >val\n    if(ss>qe || se<qs){ // completely outside our query\n        return 0;\n    }\n    if(qs<=ss && qe>=se){ // completely inside my query range\n        int idx;\n        if(type==1){\n            idx= binSearch1(seg[si], val); // max index that is smaller than val\n        }\n        else if(type==2){\n            idx= binSearch2(seg[si], val); // min index that is larger than val\n        }\n        return idx;\n    }\n    \n    int mid= ss + (se-ss)/2;\n    int leftAns= query(2*si+1, ss, mid, qs, qe, val, type);\n    int rightAns= query(2*si+2, mid+1, se, qs, qe, val, type);\n    return leftAns+rightAns;\n}\n\n\nclass Solution {\npublic:\n    int sumOfBeauties(vector<int>& nums) {\n        // Solve using segment tree (precisely merge sort segment tree)\n        int n= nums.size();\n        seg.clear(); seg.resize(4*n, {});\n        \n        build(0, 0, n-1, nums);\n        \n        int sum=0;\n        for(int i=1; i<n-1; i++){\n            int val=nums[i];\n            int q1= query(0, 0, n-1, 0, i-1, val, 1); // type 1\n            int q2= query(0, 0, n-1, i+1, n-1, val, 2); // type 2\n            \n            if( q1==i && q2==((n-1)-(i+1)+1) ){ sum+=2; }\n            else if(nums[i-1]<nums[i] && nums[i]<nums[i+1]){ sum+=1; }\n        }\n        return sum;\n    }\n};\n```\nTime Complexity: O(logN + N*2*(logN)^2) || Space Complexity: O(NlogN)
['Tree', 'C', 'Merge Sort']