#include <bits/stdc++.h>
using namespace std;
const int mod = 1e6 + 3;
int n,arr[500009];
int odd[500009],even[500009];
int freq[500009];
bool dmm[500009];
void findrange() {
//odd
int pt = 1;
for (int i = 1;i <= n;i++) {
freq[arr[i]]++;
if (i % 2 != 0) {
while (freq[arr[i]] > 1) {
freq[arr[pt]]--;
if (pt % 2 != 0) dmm[arr[pt]] = 0;
pt++;
}
dmm[arr[i]] = 1;
} else {
while (dmm[arr[i]]) {
freq[arr[pt]]--;
if (pt % 2 != 0) dmm[arr[pt]] = 0;
pt++;
}
}
odd[i] = pt;
}
//even
for (int i = 1;i <= n;i++) freq[i] = dmm[i] = 0;
pt = 1;
for (int i = 1;i <= n;i++) {
freq[arr[i]]++;
if (i % 2 == 0) {
while (freq[arr[i]] > 1) {
freq[arr[pt]]--;
if (pt % 2 == 0) dmm[arr[pt]] = 0;
pt++;
}
dmm[arr[i]] = 1;
} else {
while (dmm[arr[i]]) {
freq[arr[pt]]--;
if (pt % 2 == 0) dmm[arr[pt]] = 0;
pt++;
}
}
even[i] = pt;
}
}
int dp[500009],predp[500009];
int sumdp(int l,int r) {
l--,r--;
if (l == 0) return predp[r];
return (predp[r] - predp[l - 1] + mod)%mod;
}
//segment tree
pair <int,int> st[2][500009 * 4];
//.first: co bn segment phu doan l,r
//.second: tong cac dp duoc phu boi it nhat 1 doan trong doan l,r
void changeseg(int id,int l,int r,int u,int v,int val,pair <int,int> st[]) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[id].first += val;
if (st[id].first > 0) st[id].second = sumdp(l,r);
else if (l == r) st[id].second = 0;
else st[id].second = (st[id*2].second + st[id*2+1].second)%mod;
return;
}
int mid = (l + r) >> 1;
changeseg(id*2,l,mid,u,v,val,st);
changeseg(id*2+1,mid+1,r,u,v,val,st);
if (st[id].first > 0) st[id].second = sumdp(l,r);
else st[id].second = (st[id*2].second + st[id*2+1].second)%mod;
}
void updatevalue(int id,int l,int r,int pos) {
if (l > pos || r < pos) return;
if (l == r) {
if (st[0][id].first > 0) st[0][id].second = sumdp(l,r);
else st[0][id].second = 0;
if (st[1][id].first > 0) st[1][id].second = sumdp(l,r);
else st[1][id].second = 0;
return;
}
int mid = (l + r) >> 1;
updatevalue(id*2,l,mid,pos);
updatevalue(id*2+1,mid+1,r,pos);
if (st[0][id].first > 0) st[0][id].second = sumdp(l,r);
else st[0][id].second = (st[0][id*2].second + st[0][id*2+1].second)%mod;
if (st[1][id].first > 0) st[1][id].second = sumdp(l,r);
else st[1][id].second = (st[1][id*2].second + st[1][id*2+1].second)%mod;
}
int get(int id,int l,int r,int u,int v,pair <int,int> st[]) {
if (l > v || r < u) return 0;
if (st[id].first > 0) return sumdp(max(l,u),min(r,v));
if (l >= u && r <= v) return st[id].second;
int mid = (l + r) >> 1;
return (get(id*2,l,mid,u,v,st) + get(id*2+1,mid+1,r,u,v,st))%mod;
}
int prevodd[500009],preveven[500009];
int prevodd2[500009],preveven2[500009];
void caldp() {
dp[0] = 1;
predp[0] = 1;
for (int i = 1;i <= n;i++) {
int l,r;
//Range 1: a[i] la phan tu light
l = (i % 2 == 0 ? even[i] : odd[i]),r = i;
//tong cach tao ra dp i la so cach tao ra dp x (x thuoc [l - 1,r - 1])
//tru di nhung thang nao ma [x + 1,i] co 1 thang khac tinh cl vs i
//la light
dp[i] = (dp[i] + sumdp(l,r))%mod;
dp[i] = (dp[i] - (i % 2 == 0 ? get(1,1,n,l,r,st[1]) : get(1,1,n,l,r,st[0])) + mod)%mod;
//update range prev ai, ai
if (i % 2 == 0) {
if (preveven[arr[i]] == 0) {
changeseg(1,1,n,1,i,1,st[0]);
preveven[arr[i]] = i;
}
else {
changeseg(1,1,n,preveven2[arr[i]] + 1,preveven[arr[i]],-1,st[0]);
changeseg(1,1,n,preveven[arr[i]] + 1,i,1,st[0]);
preveven2[arr[i]] = preveven[arr[i]];
preveven[arr[i]] = i;
}
} else {
if (prevodd[arr[i]] == 0) {
changeseg(1,1,n,1,i,1,st[1]);
prevodd[arr[i]] = i;
}
else {
changeseg(1,1,n,prevodd2[arr[i]] + 1,prevodd[arr[i]],-1,st[1]);
changeseg(1,1,n,prevodd[arr[i]] + 1,i,1,st[1]);
prevodd2[arr[i]] = prevodd[arr[i]];
prevodd[arr[i]] = i;
}
}
//Range 2: a[i] la phan tu heavy -> a[i - 1] la light
if (i > 1 && arr[i] != arr[i - 1]) {
l = (i % 2 == 0 ? odd[i - 1] : even[i - 1]),r = (i % 2 == 0 ? even[i] : odd[i]) - 1;
if (l <= r) {
dp[i] = (dp[i] + sumdp(l,r))%mod;
dp[i] = (dp[i] - (i % 2 == 0 ? get(1,1,n,l,r,st[0]) : get(1,1,n,l,r,st[1])) + mod)%mod;
}
}
predp[i] = (predp[i - 1] + dp[i])%mod;
updatevalue(1,1,n,i + 1);
// cout << dp[i] << " ";
}
cout << dp[n];
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(nullptr);
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
cin >> n;
for (int i = 1;i <= n;i++) cin >> arr[i];
findrange();
caldp();
}
/*
Nho doi vai em gay
co gai ay ngoi duoi goc pho nen tho ...
*/
