P11518 [CCO 2024] Heavy Light Decomposition

翻译自 [CCO](https://cemc.uwaterloo.ca/resources/past-contests?contest_category=80) 的 [2024P5题](https://dmoj.ca/problem/cco24p5)。

在一个只包含正整数的数组中，如果一个数字在数组里多次出现，我们就称它为“重的”，否则为“轻的”。定义好的数组是指数组里的数字交替出现“轻的”元素和“重的”元素。给你一个数组 $a_{1}, \ldots, a_{N}$，请计算把它划分成若干个连续的子数组，使得每个子数组本身都是好数组的方案数。由于答案可能很大，请将最终结果对 $1000003$ 取模输出。

第一行包含一个正整数 $N$。 第二行包含 $N$ 个正整数 $a_{1}, \ldots, a_{N}\ (1 \leq a_{i} \leq N)$，表示数组中的元素。

输出一行一个整数，表示方案数对 $1000003$ 取模后的结果。

| 子任务 | 分值 | 限制 | | :----------: | :----------: | :----------: | | $1$ | $12$ | $2 \leq N \leq 50000$，对于所有的 $i$，$a_{i}\leq 26$ | | $2$ | $16$ | $2 \leq N \leq 5000$| | $3$ | $20$ | $2 \leq N \leq 5\times 10^5$，每个序号为奇数的元素 $a_{i}$ 都必须等于 $1$| | $4$ | $24$ | 数组里的每个数字最多出现两次| | $5$ | $28$ | $2 \leq N \leq 5\times 10^5$，无额外限制| 对于 $100\%$ 的数据，$2 \leq N \leq 5\times 10^5$。