minisecvente

#include <fstream>
#define NMAX 100002
#define LMAX 18
using namespace std;
ifstream f("minisecvente.in");
ofstream g("minisecvente.out");
int n,i,a[NMAX],tomp[NMAX],vio[LMAX][NMAX],ru,dont,j;
long long sol;

int minim(int st,int dr)
{
    int diff,sh,l;
    diff=dr-st+1;
	l=tomp[diff];
	sh=diff-(1<<l);
	return min(vio[l][st],vio[l][st+sh]);
}

int caut(int st,int dr)
{
    if(st>dr)
        return 0;
    else
    {
        int mij=(st+dr)/2;
        if((minim(mij,i)<i-mij+1)&&(minim(mij+1,i)>=i-mij))
            return mij;
        if(minim(mij,i)>=i-mij+1)
            return caut(st,mij);
        else
            return caut(mij+1,dr);
    }
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i];
    tomp[1]=0;
	for(i=2;i<=n;++i)
		tomp[i]=tomp[i/2]+1;
	for(i=1;i<=n;++i)
		vio[0][i]=a[i];
	for(i=1;(1<<i)<=n;++i)
		for(j=1;j<=n-(1<<i)+1;++j)
            dont=1<<(i-1),vio[i][j]=min(vio[i-1][j],vio[i-1][j+dont] );
	sol=0;
    for(i=1;i<=n;++i)
        if(minim(1,i)<i)
            ru=caut(1,i),sol+=ru;
    g<<sol;
    return 0;
}