Cod sursă (job #720046)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000003;
const int MAXN = 100002;

int N;
int A[MAXN], B[MAXN];
int D[MAXN][2], S[MAXN][2];
 
inline 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;
}
 
inline 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() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ifstream cin("sam.in");
	ofstream cout("sam.out");
	cin >> N;
	for (int i = 1; i <= N; ++i)
		cin >> 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] = S[1][0] = D[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;
		}
	}
	cout << sol << '\n';
}