Cod sursă (job #547037)

#include <std/bits++.h>

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;

		// 0 - vine din mai mic
		if (up) AddLow(D[i][0], p - 1, A[i]);
		else AddLow(D[i][0], p - 2, A[i]);

		// 1 - vine din mai mare
		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';
}


/*

pentru si din mila domnului sa fie 



*/