4170. 「CCO 2024」Heavy Light Decomposition

题目描述

译自 CCO 2024 Day2 T2「Heavy Light Decomposition」。

在一个只包含正整数的数组中，如果一个数字在数组里出现多次，我们就称它为「重」元素，否则为「轻」元素。

好的数组是指数组里的数字交替出现「轻」元素和「重」元素。

给你一个数组 $a_{1}, \ldots, a_{N}$，请计算把它划分成若干个连续的子数组，使得每个子数组本身也都是好的数组的方案数。由于答案可能很大，请将最终结果对 $1000003$ 取模输出。

输入格式

第一行包含一个正整数 $N$，表示数组的长度。

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

输出格式

输出将数组划分成好的连续子数组的方案数，对 $1000003$ 取模后的结果。

样例 1

输入

5
1 2 3 2 3

输出

4

解释

对于数组 $[1,2,3,2,3]$，存在 4 种合法的划分方式：

• $[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

输出

6

数据范围与提示