#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int MOD = 1e6+5;
int n,a[N],dp[N],pre[N][3],last[N][3];
struct segtree{
int st[4*N],mx[4*N],lazy[4*N];
vector<pii>huhu[N];
void down(int id){
if(lazy[id] != 0){
mx[2*id] += lazy[id];
mx[2*id+1] += lazy[id];
lazy[2*id] += lazy[id];
lazy[2*id+1] += lazy[id];
lazy[id] = 0;
}
}
void suc(int id){
if(mx[2*id] == mx[2*id+1]){
st[id] = (st[2*id]+st[2*id+1]) % MOD;
mx[id] = mx[2*id];
}
else if(mx[2*id] > mx[2*id+1]){
st[id] = st[2*id];
mx[id] = mx[2*id];
}
else{
st[id] = st[2*id+1];
mx[id] = mx[2*id+1];
}
}
void add(int id, int l, int r, int u, int v, int val){
if(l > v || r < u) return;
if(l >= u && r <= v){
mx[id] += val;
lazy[id] += val;
return;
}
int mid = (l+r)/2;
down(id);
add(2*id,l,mid,u,v,val);
add(2*id+1,mid+1,r,u,v,val);
suc(id);
}
void update(int id, int l, int r, int i, int val){
if(l > i || r < i) return;
if(l == r){
st[id] = val;
return;
}
int mid = (l+r)/2;
down(id);
update(2*id,l,mid,i,val);
update(2*id+1,mid+1,r,i,val);
suc(id);
}
} chan,le;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 2; j++) pre[i][j] = last[a[i]][j];
last[a[i]][0] = i;
if(i % 2 == 1) last[a[i]][1] = i;
else last[a[i]][2] = i;
}
int tot1 = 0;
int tot2 = 0;
dp[0] = 1;
for(int i = 1; i <= n; i++){
if(i % 2 == 1){
int l = pre[i][0];
le.add(1,1,n,l+1,n,1);
le.huhu[i].push_back({l+1,n});
tot1++;
int l1 = pre[i][2];
int r1 = pre[i][0];
chan.add(1,1,n,i+1,n,1);
chan.huhu[i].push_back({i+1,n});
if(l1 < r1){
chan.add(1,1,n,l1+1,r1,1);
chan.huhu[i].push_back({l1+1,r1});
}
tot2++;
if(l){
for(auto[x,y]: chan.huhu[l]) chan.add(1,1,n,x,y,-1);
tot2--;
}
}
else{
int l = pre[i][0];
chan.add(1,1,n,l+1,n,1);
chan.huhu[i].push_back({l+1,n});
tot2++;
int l1 = pre[i][1];
int r1 = pre[i][0];
le.add(1,1,n,i+1,n,1);
le.huhu[i].push_back({i+1,n});
tot1++;
if(l1 < r1){
le.add(1,1,n,l1+1,r1,1);
le.huhu[i].push_back({l1+1,r1});
}
if(l){
for(auto[x,y]: le.huhu[l]) le.add(1,1,n,x,y,-1);
tot1--;
}
}
if(chan.mx[1] == tot2) dp[i] += chan.st[1];
if(le.mx[1] == tot1) dp[i] += le.st[1];
dp[i] = (dp[i]+dp[i-1]) % MOD;
le.update(1,1,n,i,dp[i]);
chan.update(1,1,n,i,dp[i]);
}
cout << dp[n];
}
