<p>You may recall that an array <code>arr</code> is a <strong>mountain array</strong> if and only if:</p>

<ul>
	<li><code>arr.length &gt;= 3</code></li>
	<li>There exists some index <code>i</code> (<strong>0-indexed</strong>) with <code>0 &lt; i &lt; arr.length - 1</code> such that:
	<ul>
		<li><code>arr[0] &lt; arr[1] &lt; ... &lt; arr[i - 1] &lt; arr[i]</code></li>
		<li><code>arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]</code></li>
	</ul>
	</li>
</ul>

<p>Given an integer array <code>nums</code>​​​, return <em>the <strong>minimum</strong> number of elements to remove to make </em><code>nums<em>​​​</em></code><em> </em><em>a <strong>mountain array</strong>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,1]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The array itself is a mountain array so we do not need to remove any elements.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,1,5,6,2,3,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li>It is guaranteed that you can make a mountain array out of <code>nums</code>.</li>
</ul>

class Solution {
public:
     class segmentTree{
vector<int>seg,a;
int len;
public:
segmentTree(int n){
  seg.resize(4*n,0);
  len=4*n;
}
int getmin(int index,int low,int high,int l,int r){
  if(low>=l && high<=r){
    return seg[index];
  }
  if(high<l || low>r){return 0;}
  int mid=(low+high)/2;
  int left=getmin(2*index+1,low,mid,l,r);
  int right=getmin(2*index+2,mid+1,high,l,r);
  return max(left,right);
}

void update(int index,int low ,int high,int i,int value){
  if(low==high && low==i) {
    seg[index]=value; return;
  }
  if(low>i || high<i) return;
  int mid=(low+high)/2;
  update(2*index+1,low,mid,i,value);
  update(2*index+2,mid+1,high,i,value);
  seg[index]=max(seg[2*index+1],seg[2*index+2]);
}

int getmin(int l,int r){
    return getmin(0,0,len/4-1,l,r);
}

void update(int i,int value){
    update(0,0,len/4-1,i,value);
}
};

    int our_index(vector<int>&a,int num){
        int x=lower_bound(a.begin(),a.end(),num)-a.begin();
        return x;
    }
    int minimumMountainRemovals(vector<int>& nums) {
       // lcs with last element less than peak element
        set<int>s;
        vector<int>a;
        for(auto i:nums) s.insert(i);
        for(auto i:s) a.push_back(i);
        int peak=0;
        int n=nums.size();
        vector<int>pref(n+1,0);
        segmentTree Tr(n+1);
        int index=our_index(a,nums[0]);
        Tr.update(index,1);
        pref[0]=0;
        for(int peak=1;peak<n;peak++){
            int index=our_index(a,nums[peak]);
            int ans=Tr.getmin(0,index-1);
                        pref[peak]=ans;
         //   cout<<ans<<" "<<index<<endl;
            ans++;
            
            Tr.update(index,ans);
        }
      //  for(auto i:pref) cout<<i<<" "; cout<<endl;
        segmentTree Tr2(n+1);
        reverse(nums.begin(),nums.end());
        vector<int>pref2(n+1);
          index=our_index(a,nums[0]);
        Tr2.update(index,1);
        pref2[0]=0;
        for(int peak=1;peak<n;peak++){
            int index=our_index(a,nums[peak]);
            int ans=Tr2.getmin(0,index-1);
            pref2[peak]=ans;
            ans++;
            
            Tr2.update(index,ans);
        }
           // pref2[0]-> last 1
        // pref1[n-2]
        // pref2[1]
        // pref[n-3]
      
      
        int finalans=n;
        for(int i=0;i<n-1;i++){
            int x=pref[i]+pref2[n-1-i]+1;
             //cout<<i<<" "<<n-1-i<<endl;
            if(pref[i]==0 || pref2[n-1-i]==0 ) continue;
           
            finalans=min(finalans,n-x);
            cout<<finalans<<" "<<i<<" "<<n-1-i<< endl;
        }
        return finalans;
    }
};
20500