Cod sursă (job #547286)

#include <bits/stdc++.h>
#define Dim 10001
#define MOD 1000003
using namespace std;

ifstream fin("sam.in");
ofstream fout("sam.out");

//const int MOD = 1000003;
//const int Dim = 100002;
int N;
int A[Dim], B[Dim];
int D[Dim][2], S[Dim][2];

void AddLow(int &x, int p, int v)
{
    if (p == 0)
    {
        ++x;
        if (x >= MOD) x -= MOD;
        return;
    }
    if (A[B[p]] > v) return;

    int lim1 = (p == 1 ? 1 : B[p - 1] + 1);
    int lim2 = (p == B[0] ? N : B[p + 1] - 1);
    if (lim1 > lim2) return;

    int p2, b1 = B[p], b2 = B[p];
    for (p2 = (1 << 16); p2; p2 >>= 1)
        if (b1 - p2 >= lim1 && A[b1 - p2] < v)
            b1 -= p2;
    for ( p2 = (1 << 16); p2; p2 >>= 1)
        if (b2 + p2 <= lim2 && A[b2 + p2] < v)
            b2 += p2;

    x += S[b2][1] - S[b1 - 1][1];
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

void AddHigh(int &x, int p, int v)
{
    if (p == 0)
    {
        ++x;
        if (x >= MOD) x -= MOD;
        return;
    }
    if (A[B[p]] < v) return;

    int lim1 = (p == 1 ? 1 : B[p - 1] + 1);
    int lim2 = (p == B[0] ? N : B[p + 1] - 1);
    if (lim1 > lim2) return;

    int p2, b1 = B[p], b2 = B[p];
    for (p2 = (1 << 16); p2; p2 >>= 1)
        if (b1 - p2 >= lim1 && A[b1 - p2] > v)
            b1 -= p2;
    for ( p2 = (1 << 16); p2; p2 >>= 1)
        if (b2 + p2 <= lim2 && A[b2 + p2] > v)
            b2 += p2;

    x += S[b2][0] - S[b1 - 1][0];
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

int main()
{

    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> A[i];

    B[++B[0]] = 1;
    for ( int i = 2; i <= N - 1; ++i )
        if (A[i] < A[i - 1] && A[i] < A[i + 1])
            B[++B[0]] = i;
        else if (A[i] > A[i - 1] && A[i] > A[i + 1])
            B[++B[0]] = i;

    B[++B[0]] = N;
    D[1][0] = 1;
    S[1][0] = 1;
    D[1][1] = 1;
    S[1][1] = 1;

    int p = 1;
    for ( int i = 2; i <= N; ++i )
    {
        if (i > B[p])
            ++p;

        bool up = false;
        if (i == B[p] && A[i] > A[i - 1]) up = true;
        if (i != B[p] && A[i] < A[i + 1]) up = true;

        if (up)  AddLow(D[i][0], p - 1, A[i]);
        else     AddLow(D[i][0], p - 2, A[i]);

        if (up)  AddHigh(D[i][1], p - 2, A[i]);
        else     AddHigh(D[i][1], p - 1, A[i]);

        S[i][0] = S[i - 1][0] + D[i][0];
        if (S[i][0] >= MOD) S[i][0] -= MOD;
        S[i][1] = S[i - 1][1] + D[i][1];
        if (S[i][1] >= MOD) S[i][1] -= MOD;
    }

    int sol = 0;
    if (A[N] > A[N - 1])
    {
        sol = D[N][0];
        for (int i = N - 1; i >= 2 && A[i] > A[i - 1]; --i)
        {
            sol += D[i][0];
            if (sol >= MOD) sol -= MOD;
        }
    }
    else
    {
        sol = D[N][1];
        for (int i = N - 1; i >= 2 && A[i] < A[i - 1]; --i)
        {
            sol += D[i][1];
            if (sol >= MOD) sol -= MOD;
        }
    }

    fout << sol << '\n';

    fin.close();
    fout.close();
}