#include <stdio.h>
#include <string.h>
#define N 500000
#define N_ (1 << 19) /* N_ = pow2(ceil(log2(N))) */
#define MD 1000003
int min(int a, int b) { return a < b ? a : b; }
int ss[2][N_ * 2], qq[2][N_ * 2], xx[2][N_ * 2], n_, t;
void pul(int i) {
int l = i << 1, r = l | 1, ql, qr;
ss[t][i] = ss[t][l] + ss[t][r];
ql = qq[t][l] + ss[t][r], qr = qq[t][r];
if (ql < qr)
qq[t][i] = ql, xx[t][i] = xx[t][l];
else if (ql > qr)
qq[t][i] = qr, xx[t][i] = xx[t][r];
else
qq[t][i] = ql, xx[t][i] = (xx[t][l] + xx[t][r]) % MD;
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
void update_x(int i, int x) {
i += n_;
xx[t][i] = x, pull(i);
}
void update_d(int i, int d) {
i += n_;
qq[t][i] = ss[t][i] += d, pull(i);
}
int main() {
static int ii[N], pp[N], dp[N + 1];
int n, i, j, a;
scanf("%d", &n);
n_ = 1;
while (n_ <= n)
n_ <<= 1;
dp[0] = 1;
for (t = 0; t < 2; t++)
update_x(0, dp[0]);
memset(ii, -1, n * sizeof *ii);
for (j = 0; j < n; j++) {
scanf("%d", &a), a--;
pp[j] = i = ii[a], ii[a] = j;
for (t = 0; t < 2; t++) {
if (j % 2 == t) {
if (i != -1)
update_d(i, 1);
} else {
update_d(j, 1);
if (i != -1 && i % 2 != t) {
update_d(i, -2);
if (pp[i] != -1)
update_d(pp[i], 1);
}
}
dp[j + 1] = (dp[j + 1] + xx[t][1]) % MD;
}
for (t = 0; t < 2; t++)
update_x(j + 1, dp[j + 1]);
}
printf("%d\n", dp[n]);
return 0;
}
