Cod sursă (job #720016)

#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;
//ifstream fi("sam.in");
//ofstream fo("sam.out");
pair<int,int>a[2][100005],nr;
int n,A[100005],ans,maxim;
 
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<=l){
		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(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(){
	ifstream cin("sam.in");
	ofstream cout("sam.out");
    cin >> n;
    for(int i=1;i<=n;i++){
    	cin >> A[i];	
	}
    ans=1;
    maxim=1;
    update(0,1,1,n,A[1],{1,2});
    update(1,1,1,n,A[1],{1,2});
    for(int i=2;i<=n;i++){
        nr={1,1};
        query(0,1,1,n,A[i],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[i],nr);
        nr={1,1};
        query(1,1,1,n,1,A[i]-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[i],nr);
    }
    cout << ans << endl;
    return 0;
}