#include <cstdio> #include <algorithm> #include <cstring> #ifndef ONLINE_JUDGE #define FILEIO #endif // ONLINE_JUDGE #ifdef FILEIO FILE *infile=fopen("height.in","r"), *outfile=fopen("height.out","w"); #define scanf(x...) fscanf(infile,x) #define printf(x...) fprintf(outfile,x) #endif // FILEIO int n,x; int T[1000002]; inline int lowbit(int x) { return x&(-x); } inline void add(int x,int i) { while(x<=n+1) { T[x]=std::min(T[x],i); x+=lowbit(x); } } inline int query(int N) { int res=2147483647; while(N) { res=std::min(res,T[N]); N-=lowbit(N); } if(res>=n) return 0; return res; } int main() { scanf("%d",&n); memset(T,0x7f,sizeof(T)); int ans=0,tmp; for(int i=1;i<=n;++i) { scanf("%d",&x); tmp=query(n-x); if(tmp) ans+=i-tmp; add(n+1-x,i); } printf("%d\n",ans); #ifdef FILEIO fclose(infile); fclose(outfile); #undef scanf #undef printf #endif // FILEIO return 0; }