week14- D. Edit Sequence, Author Solution

#include <bits/stdc++.h>
using namespace std;
const int INF = 1023456789;
const int SIZE = 200002;
int A[SIZE],left_mi[SIZE],right_ma[SIZE];
int solve(vector<int>& seq){
    int now=0,ret;
    for(int i=0;i<seq.size();i++){
        if(seq[i]!=seq[0])now++;
    }
    ret=now;
    for(int i=0;i<seq.size();i++){
        if(seq[i]==seq[0])now++;
        else now--;
        ret=min(ret,now);
    }
    return ret;
}
int main(){
    int N,h=0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)scanf("%d",&A[i]);
    left_mi[0]=INF;
    for(int i=1;i<=N;i++){
        left_mi[i]=min(left_mi[i-1],A[i]);
    }
    right_ma[N+1]=-INF;
    for(int i=N;i>0;i--){
        right_ma[i]=max(right_ma[i+1],A[i]);
        h=max(h,right_ma[i]-left_mi[i-1]);
    }
    int low=INF,an=0;
    vector<int>seq;
    for(int i=1;i<=N;i++){
        if(A[i]<low){
            an+=solve(seq);
            seq.clear();
            low=A[i];
        }
        if(A[i]==low+h)seq.push_back(A[i]);
        else if(A[i]==low&&right_ma[i+1]==low+h)seq.push_back(A[i]);
    }
    an+=solve(seq);
    printf("%d\n",an);
    return 0;
}