Cod sursă (job #687888)

#include <bits/stdc++.h>
#include <unordered_map>
#include <map>

using namespace std;

ifstream fin("sam.in");
ofstream fout("sam.out");
//-----------------------------------------
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
//-----------------------------------------
#define f(i,s,e) for(int i=s;i<=e;++i)
#define nf(i,s,e) for(i=s;i<e;++i)
#define rf(i,e,s) for(i=e;i>=s;--i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sp <<" "
//------------------------------------------
const int NMAX = 1e5 + 20;
const int KMAX = 1e1 + 5;
const int MOD = 1e6 + 3;
const int INF = 0x3f3f3f3f;
//------------------------------------------
struct uc {
    int a[2];
}b[100010];
int n;
int v[NMAX], aux[NMAX];
//------------------------------------------
void read() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    if (v[1] < v[2])
        v[0] = n + 1;
    if (v[n - 1] < v[n])
        v[n + 1] = -1;
    else v[n + 1] = n + 2;
    aux[1] = 1;
}
void solve() {
    int k = 1, s = 0, t;
    if (v[0] < v[1])s = 1;
    for (int i = 2; i <= n + 1; i++) {
        t = 0;
        if (v[i - 1] < v[i])
            t = 1;
        if (s == t) {
            k++;
            aux[k] = i - 1;
            s = 1 - s;
        }
    }
    k++;
    aux[k] = n + 1;
    s = 0;
    if (v[0] < v[1])
        s = 1;
    for (int i = aux[0] + 1; i <= aux[2] - 1; i++)
        b[i].a[s] = 1;
    for (int p = 1; p <= k - 2; p++) {
        s = 1 - s;
        for (int i = aux[p] + 1; i <= aux[p + 2] - 1; i++) {
            for (int j = aux[p - 1]; j <= aux[p + 1] - 1 && j <= i - 1; j++) {
                t = 0;
                if (v[j] < v[i])
                    t = 1;
                if (s == t) {
                    b[i].a[s] += b[j].a[1 - s];
                    b[i].a[s] = b[i].a[s] % MOD;
                }
            }
        }
    }
    int nr = 0;
    for (int i = aux[k - 2]; i <= aux[k] - 1; i++) {
        nr += b[i].a[s];
    }
    fout << nr % MOD;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    read();
    solve();
    return 0;
}