Cod sursă (job #542985)

#include<fstream>
using namespace std;

ifstream  fin("sam.in");
ofstream fout("sam.out");
int n,i,j,k,p,a[100009],x[100009],dir,v;
int  b[2][100009];

int main()
{
    fin>>n;
    for (i=1;i<=n;i++){
        fin>>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]=-1;
    x[1]=0;
    p=1;
    for(i=1;i<=n;i++)
    {
        if((a[i-1]<a[i] && a[i]>a[i+1])||
           (a[i-1]>a[i] && a[i]<a[i+1]))
           {
               p++;
               x[p]=i;
           }
    }
    x[p+1]=n+1;
    x[p+2]=n+2;

    if(a[1]<a[2])dir=0;
    else dir=1;

    b[dir][0]=1;
    for (k=1;k<=p;k++)
    {
        dir=1-dir;
        for(i=1+x[k-1];i<x[k+1];i++)
        {
		v=(x[k]>i)?x[k]:i;
            for(j=1+v;j<x[k+2];j++)
            {
                if((a[j]>a[i] && dir==0) ||
                  (a[j]<a[i] && dir==1))
                {
                    b[dir][j]=(b[dir][j]+b[1-dir][i])%1000003;
                }
            }
        }
    }
    fout<<b[dir][n]<<"\n";
    fout.close();
    fin.close();
    return 0;
}