document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1023456789;
  4. const int SIZE = 200002;
  5. int A[SIZE],left_mi[SIZE],right_ma[SIZE];
  6. int solve(vector<int>& seq){
  7.     int now=0,ret;
  8.     for(int i=0;i<seq.size();i++){
  9.         if(seq[i]!=seq[0])now++;
  10.     }
  11.     ret=now;
  12.     for(int i=0;i<seq.size();i++){
  13.         if(seq[i]==seq[0])now++;
  14.         else now--;
  15.         ret=min(ret,now);
  16.     }
  17.     return ret;
  18. }
  19. int main(){
  20.     int N,h=0;
  21.     scanf("%d",&N);
  22.     for(int i=1;i<=N;i++)scanf("%d",&A[i]);
  23.     left_mi[0]=INF;
  24.     for(int i=1;i<=N;i++){
  25.         left_mi[i]=min(left_mi[i-1],A[i]);
  26.     }
  27.     right_ma[N+1]=-INF;
  28.     for(int i=N;i>0;i--){
  29.         right_ma[i]=max(right_ma[i+1],A[i]);
  30.         h=max(h,right_ma[i]-left_mi[i-1]);
  31.     }
  32.     int low=INF,an=0;
  33.     vector<int>seq;
  34.     for(int i=1;i<=N;i++){
  35.         if(A[i]<low){
  36.             an+=solve(seq);
  37.             seq.clear();
  38.             low=A[i];
  39.         }
  40.         if(A[i]==low+h)seq.push_back(A[i]);
  41.         else if(A[i]==low&&right_ma[i+1]==low+h)seq.push_back(A[i]);
  42.     }
  43.     an+=solve(seq);
  44.     printf("%d\\n",an);
  45.     return 0;
  46. }
');