#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll mod = 1000003;
struct Node{
ll mn, sum;
};
Node Merge(Node u, Node v) {
Node ret;
ret.mn = min(u.mn, v.mn);
ret.sum = 0;
if (u.mn == ret.mn) ret.sum += u.sum;
if (v.mn == ret.mn) ret.sum += v.sum;
ret.sum %= mod;
return ret;
}
struct SegmentTree{
vector<Node> tree;
vector<ll> lazy;
void init(ll n) {
int sz = 1 << __lg(n-1) + 2;
tree.assign(sz, {0, 0});
lazy.assign(sz, 0);
}
void propagate(ll node, ll s, ll e) {
if (!lazy[node]) return;
tree[node].mn += lazy[node];
if (s != e) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
void update(ll node, ll s, ll e, ll l, ll r, ll v) {
propagate(node, s, e);
if (l > e || s > r) return;
if (l <= s && e <= r) {
lazy[node] = v;
propagate(node, s, e);
return;
}
ll mid = s + e >> 1;
update(node*2, s, mid, l, r, v);
update(node*2+1, mid+1, e, l, r, v);
tree[node] = Merge(tree[node*2], tree[node*2+1]);
}
void modify(ll node, ll s, ll e, ll tar, ll val) {
propagate(node, s, e);
if (s > tar || tar > e) return;
if (s == e) {
tree[node].sum += val;
tree[node].sum %= mod;
return;
}
ll mid = s + e >> 1;
modify(node*2, s, mid, tar, val);
modify(node*2+1, mid+1, e, tar, val);
tree[node] = Merge(tree[node*2], tree[node*2+1]);
}
ll Get() {
if (tree[1].mn == 0) return tree[1].sum;
return 0;
}
};
ll a[500010];
ll dp[500010];
SegmentTree seg[2];
vector<ll> pos[500010];
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
ll N;
cin >> N;
for (ll i=1; i<=N; i++) {
cin >> a[i];
pos[i].push_back(0);
}
seg[0].init(N);
seg[1].init(N);
dp[0] = 1;
seg[0].modify(1, 1, N, 1, 1);
seg[1].modify(1, 1, N, 1, 1);
for (ll i=1; i<=N; i++) {
ll v = a[i];
seg[i&1].update(1, 1, N, 1, pos[v].back(), 1);
if (pos[v].back() % 2 != i % 2) {
seg[i&1^1].update(1, 1, N, 1, i, 1);
}
else {
seg[i&1^1].update(1, 1, N, pos[v].back()+1, i, 1);
if (pos[v].size() >= 2) {
seg[i&1^1].update(1, 1, N, pos[v][pos[v].size()-2]+1, pos[v].back(), -1);
}
}
pos[v].push_back(i);
dp[i] = (seg[0].Get() + seg[1].Get()) % mod;
if (i < N) {
seg[0].modify(1, 1, N, i+1, dp[i]);
seg[1].modify(1, 1, N, i+1, dp[i]);
}
}
cout << dp[N] << '\n';
}
