Cod sursă (job #720020)

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define mod 1000003
using namespace std;
const int maxn=1e5+5;
pair<int,int> A[2][4*maxn],nr;
int n,ans,maxim,a;
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
pair<int,int> comb(pair<int,int> a, pair<int,int> b){
    pair<int,int> ans={0,0};
    ans.S=max(a.S,b.S);
    if(ans.S==a.S)
        ans.F=(ans.F+a.F)%mod;
    if(ans.S==b.S)
        ans.F=(ans.F+b.F)%mod;
    return ans;
}
 
void update(int t,int node,int l,int r,int u,pair<int,int> val){
    if(l==r){
        A[t][node]=comb(A[t][node],val);
        return;
    }
    int mid=(l+r)/2;
    if(u<=mid) update(t,2*node,l,mid,u,val);
    else{
    	update(t,2*node+1,mid+1,r,u,val);	
	}
    A[t][node]=comb(A[t][2*node],A[t][2*node+1]);
}
 
void query(int t,int node,int l,int r,int ql,int qr){
    if(l>r) return;
    if(ql<=l&&r<=qr){
        nr=comb(nr,A[t][node]);
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid){
    	query(t,2*node,l,mid,ql,qr);	
	}
    if(qr>mid){
    	query(t,2*node+1,mid+1,r,ql,qr);	
	}
}
int main(){
	InParser fin("sam.in");
	ofstream fout("sam.out");
    fin >> n;
    ans=1;
    maxim=1;
    fin >> a;
    update(0,1,1,n,a,{1,2});
    update(1,1,1,n,a,{1,2});
    for(int i=2;i<=n;i++){
        fin >> a;
        nr={1,1};
        query(0,1,1,n,a,n);
        if(nr.S>maxim){
            maxim=nr.S;
            ans=0;
        }
        if(nr.S==maxim)ans=(ans+nr.F)%mod;
        nr.S++;
        update(1,1,1,n,a,nr);
        nr={1,1};
        query(1,1,1,n,1,a-1);
        if(nr.S>maxim){
            maxim=nr.S;
            ans=0;
        }
        if(nr.S==maxim)ans=(ans+nr.F)%mod;
        nr.S++;
        update(0,1,1,n,a,nr);
    }
	fout << ans << endl;
    return 0;
}