페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8267
서브태스크

Heavy Light Decomposition 4s 1024MB

문제

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

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

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


입력

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

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


출력

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


부분문제

번호 점수 조건
#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


예제 #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] 


예제 #2

5
1 2 1 3 1
6

출처

CCO 2024

로그인해야 코드를 작성할 수 있어요.