Page not loading? Try clicking here.
Placeholder

#8267
Subtask

Heavy Light Decomposition 4s 1024MB

Problems

양의 정수만 포함된 배열에서, 정수가 "heavy"라고 정의되면 배열에서 두 번 이상 나타나는 정수이고, "light"는 배열에서 한 번만 나타나는 정수입니다.

배열이 "good"하려면, 배열의 정수들이 "light"와 "heavy"가 번갈아 가며 나타나야 합니다.

배열 a_1, a_2, \dots, a_N에 대해, 배열을 몇 개의 연속된 부분 배열로 나누는 방법 중 각 부분 배열이 "good"한 배열이 되도록 하는 방법의 수를 구하십시오. 답이 매우 클 수 있으므로, 1,000,003으로 나눈 나머지를 출력하세요.


Input

첫 번째 줄에 정수 N이 주어집니다.

두 번째 줄에 N개의 정수 a_1, a_2, \dots, a_N이 주어집니다. (1 \leq a_i \leq N)


Output

배열을 "good"한 연속된 부분 배열로 나누는 방법의 수를 1,000,003으로 나눈 나머지를 출력합니다.


Subtask

# Score Condition
#110

2 \le N \le 50,000, a_i \le 26

#210

2 \le N \le 5,000

#320

2 \le N \le 500,000, i가 홀수 일 때 a_i=1

#427

2 \le N \le 500,000, 각 수는 배열에서 최대 두 번까지만 나타남.

#533

2 \le N \le 500,000


Example #1

5
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] 


Example #2

5
1 2 1 3 1
6

Source

CCO 2024

You must sign in to write code.