Cod sursă (job #542795)

#include<bits/stdc++.h>
using namespace std;
int n,a[100010],x[100010],nr;
struct uc{
    int v[2];
};
uc b[100010];
int main(){
	ifstream cin("sam.in");
    ofstream cout("sam.out");
    int i,s,t,j,k,p;
    cin>>n;
    for (i=1;i<=n;i++){
        cin>>a[i];
    }
    if(a[1]<a[2])a[0]=n+1;
    else a[0]=0;
    if(a[n-1]<a[n])a[n+1]=-1;
    else a[n+1]=n+2;
    x[0]=0;
    x[1]=1;
    k=1;
    s=0;
    if(a[0]<a[1])s=1;
    for (i=2;i<=n+1;i++){
        t=0;
        if(a[i-1]<a[i])
            t=1;
        if(s==t){
            k++;
            x[k]=i-1;
            s=1-s;
        }
    }
    k++;
    x[k]=n+1;
    s=0;
    if(a[0]<a[1])s=1;
    for (i=x[0]+1;i<=x[2]-1;i++){
        b[i].v[s]=1;
    }
    for (p=1;p<=k-2;p++){
        s=1-s;
        for (i=x[p]+1;i<=x[p+2]-1;i++){
            for (j=x[p-1];j<=x[p+1]-1 && j<=i-1;j++){
                t=0;
                if(a[j]<a[i])
                    t=1;
                if(s==t){
                    b[i].v[s]+=b[j].v[1-s];
                    b[i].v[s]=b[i].v[s]%1000003;
                }
            }
        }
    }
    nr=0;
    for(i=x[k-2];i<=x[k]-1;i++){
        nr+=b[i].v[s];
    }
    cout<<nr%1000003;
    return 0;
}