bdfz_2024_summer/day11/P3608/P3608.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct Cow{
    int dir;
    int h;
};

const int MAX_N = 1e5+5;
Cow cow[MAX_N];
int ans=0;

struct Tree{
    int t[MAX_N];
    int n;
    // template<typename  T>
    // Tree(const &)=delete;
    Tree(int n):n(n){}
    int lowbit(int x){
        return x&(-x);
    }
    void update(int dir,int delta){
        while(dir<=n){
            t[dir]+=delta;
            dir+=lowbit(dir);
        }
    }
    int query1to(int dir){
        int sum=0;
        while(dir>0){
            sum+=t[dir];
            dir-=lowbit(dir);
        }
        return sum;
    }
};

int readint();

signed main(){
    const int n =readint();
    for(int i=1;i<=n;i++){
        cow[i]={
            .dir=i,
            .h=readint(),
        };
    }
    sort(cow+1,cow+n+1,[](Cow a,Cow b)->bool{
        return a.h>b.h;
    });
    Tree cmax(n);
    for(int i=1;i<=n;i++){
        int l=cmax.query1to(cow[i].dir);
        int r = i-l-1;
        if(max(l,r)>min(l,r)*2)ans++;
        cmax.update(cow[i].dir, 1);
    }
    cout<<ans<<endl;
}


int readint(){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*w;
}