#define ssh(x)<x>
#include ssh(bits/stdc++.h)
#define rfor(x...)for(register x)
#define rep(i,l,r)rfor(ll i=l;i<=r;i++)
#define ref(i,l,r)rfor(ll i=l;i<r;i++)
#define per(i,l,r)rfor(ll i=l;i>=r;i--)
#define rev(i,u,v)rfor(ll i=head[u],v;v=to[i],i;i=next[i])
#define rej(i,s)rfor(ll i=s;i;i=(i-1)&(s))
#define re0(i,s)rfor(ll i=s;~i;i=i?(i-1)&(s)):-1)
#define red(i,n)rfor(ll i=n;i;i>>=1)
#define IO(x...)((*#x!='/'||#x[1])&&(*#x&&freopen(#x".in","r",stdin)&&freopen(#x".out","w",stdout),gc=fgc,pc=fpc,atexit(fout)))
typedef long long ll;
typedef const ll cll;
typedef unsigned long long ull;
cll N=4e6+7,mod=1e9+7,iv2=(mod+1)/2,iz=1<<21,oz=1<<22;
typedef ll aN[N];
char is[iz],*i1=is,*i2=is,os[oz],*o1=os,*o2=os+oz;
int fgc(){
    return i1==i2&&is==(i2=is+fread(i1=is,1,iz,stdin))?-1:*i1++;
}
void fout(){
    fwrite(os,o1-os,1,stdout),o1=os;
}
int fpc(int c){
    if(o1==o2)fout();
    return*o1++=c;
}
int(*gc)()=getchar,(*pc)(int)=putchar,wt[126];
int readchar(int l=33,int r=126){
    if(l>r)std::swap(l,r);
    int c=gc();
    for(;c<l||c>r;c=gc());
    return c;
}
ll readll(){
    ll x=0,w=1;
    int c=gc();
    for(;c<48||c>57;c=gc())c-45||(w=-w);
    for(;c>47&&c<58;c=gc())x=x*10+c-48;
    return x*w;
}
void writell(cll u,int c=32){
    int t=0;
    rfor(ull n=u<0?pc(45),0ull-u:u;n;n/=10)wt[++t]=n%10^48;
    for(t||pc(48);t;)pc(wt[t--]);
    c&&pc(c);
}
int mygets(char*s,int c=0){
    char*t=s+1;
    while((*s=gc())<33);
    while((*t=gc())>32)t++;
    c&&(*t++=c),*t=0;
    return t-s;
}
int myputs(const char*s,int c=10){
    const char*t=s;
    while(*t)pc(*t++);
    c&&pc(c);
    return t-s+(c!=0);
}
void writeull(ull u,int c=32){
    int t=0;
    rfor(ull n=u;n;n/=10)wt[++t]=n%10^48;
    for(t||pc(48);t;)pc(wt[t--]);
    c&&pc(c);
}
cll IO_res=IO(match),T=1,S=0;//readll();
void init(){
}
struct sgt{
    aN f,t;
    ll n;
    void pushup(cll u){
        f[u]=f[u<<1]*t[u<<1]+f[u<<1|1]*t[u<<1|1];
    }
    //aN z;
    void set(cll n_){
        n=2<<(31^__builtin_clz(n_+3));
        memset(f,0,sizeof f);
        rep(i,1,n_)f[i+n]=1;
        rep(i,1,n*2+4)t[i]=1;
        //per(i,n*2,n)printf("%lld %lld\n",i,f[i]);
        per(i,n-1,1)pushup(i);//,printf("%lld %lld\n",i,f[i]);
        //printf("%lld\n",f[1]);
        //rep(i,1,n_)z[i]=1;
    }
    void update1(ll l,ll r,cll c){
        //printf("%lld %lld * %lld\n",l,r,c);
        //rep(i,l,r)z[i]*=c;
        //return;
        for(l+=n-1,r+=n+1;l^r^1;l>>=1,r>>=1,pushup(l),pushup(r))
        ~l&1&&(t[l^1]*=c),r&1&&(t[r^1]*=c);
        red(i,l>>1)pushup(i);
        //per(i,n-1,1)pushup(i);
    }
    void update2(ll l,ll r,cll c){
        //printf("%lld %lld / %lld\n",l,r,c);
        //rep(i,l,r)z[i]/=c;
        //return;
        for(l+=n-1,r+=n+1;l^r^1;l>>=1,r>>=1,pushup(l),pushup(r))
        ~l&1&&(t[l^1]/=c),r&1&&(t[r^1]/=c);
        red(i,l>>1)pushup(i);
        //per(i,n-1,1)pushup(i);
    }
    ll getans()const{
        //ll res=0;
        //rep(i,1,n)res+=z[i];
        //return res;
        return f[1];
    }
}dt;
aN st1,st2,a,b;
void calc(){
    cll n=2.5e5;
    rep(i,1,n)a[i]=i;
    rep(i,1,n)b[i]=i;
    std::random_shuffle(a+1,a+n+1);
    std::random_shuffle(b+1,b+n+1);
    if(S<=13){
        cll m=5;
        dt.set(n);
        rep(s,1,m){
            cll l=1,r=n;
            //if(s!=2)continue;
            ull ans=0;
            ll t1=0,t2=0;
            st1[0]=l-1,st2[0]=l-1;
            rep(i,l,r){
                /*while(t1&&a[st1[t1]]<=a[i])
                dt.update2(st1[t1-1]+1,st1[t1],a[st1[t1]]),
                dt.update1(st1[t1-1]+1,st1[t1],a[i]),t1--;
                st1[++t1]=i,dt.update1(i,i,a[i]);
                while(t2&&b[st2[t2]]<=b[i])
                dt.update2(st2[t2-1]+1,st2[t2],b[st2[t2]]),
                dt.update1(st2[t2-1]+1,st2[t2],b[i]),t2--;
                st2[++t2]=i,dt.update1(i,i,b[i]);*/
                while(t1&&a[st1[t1]]<=a[i])
                dt.update2(st1[t1-1]+1,st1[t1],a[st1[t1]]),t1--;
                st1[++t1]=i,dt.update1(st1[t1-1]+1,st1[t1],a[i]);
                while(t2&&b[st2[t2]]<=b[i])
                dt.update2(st2[t2-1]+1,st2[t2],b[st2[t2]]),t2--;
                st2[++t2]=i,dt.update1(st2[t2-1]+1,st2[t2],b[i]);
                ans+=dt.getans()-(n-(i-l+1));
                //printf("%lld ",dt.getans());
            //rep(i,1,n)printf("%lld ",dt.z[i]);puts("");
            }
            //puts("");
            while(t1)dt.update2(st1[t1-1]+1,st1[t1],a[st1[t1]]),t1--;
            while(t2)dt.update2(st2[t2-1]+1,st2[t2],b[st2[t2]]),t2--;
            writeull(ans,10);
            //exit(0);
        }
    }
}
int main(){
    init();
    rep(i,1,T)calc();
    return 0;
}
/*
3 2
1 2
1 3
*/
