对于一个仅包含正整数的数组，如果一个整数在数组中出现超过一次，我们称其为“重数”（heavy），否则称其为“轻数”（light）。
如果一个数组中的整数在轻数和重数之间交替出现，则称该数组是“好的”（good）。
给定一个数组 $a_1, \dots, a_N$，计算将其划分为若干个连续子数组的方法数，使得每个子数组在自身看来都是“好的”。由于答案可能很大，请输出其对 $1\,000\,003$ 取模的结果。
输入格式
第一行包含一个整数 $N$。
下一行包含 $N$ 个整数 $a_1, \dots, a_N$ ($1 \le a_i \le N$)。
| 分值 | $N$ 的范围 | 附加约束 |
|---|---|---|
| 3 分 | $2 \le N \le 50\,000$ | 对于每个 $i$，$a_i \le 26$ |
| 4 分 | $2 \le N \le 5\,000$ | 无附加约束 |
| 5 分 | $2 \le N \le 500\,000$ | 若 $i$ 为奇数，则 $a_i = 1$ |
| 6 分 | $2 \le N \le 500\,000$ | 数组中任何数字最多出现两次 |
| 7 分 | $2 \le N \le 500\,000$ | 无附加约束 |
输出格式
将数组划分为若干个好的连续子数组的方法数，对 $1\,000\,003$ 取模。
样例
输入 1
5 1 2 3 2 3
输出 1
4
说明 1
对于 $[1, 2, 3, 2, 3]$，有四种合法的划分方式：
- $[1], [2], [3], [2], [3]$
- $[1], [2, 3, 2], [3]$
- $[1], [2], [3, 2, 3]$
- $[1, 2, 3, 2], [3]$
输入 2
5 1 2 1 3 1
输出 2
6