Heavy Light Decomposition

시간 제한4초메모리 제한1024 MB

요약

배열을 연속한 구간으로 나눌 때, 각 구간 안에서 한 번만 나오는 값과 두 번 이상 나오는 값이 번갈아 나타나야 한다. 이런 분할의 가짓수를 1000003으로 나눈 나머지로 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 분할 정복, 누적 합, 해시맵
정답자: 아직 제출이 없습니다

문제

In an array containing only positive integers, we say an integer is heavy if it appears more than once in the array, and light otherwise.

An array is good if the integers in the array alternate between light and heavy.

Given an array $a\_1, \dots , a\_N$ , count the number of ways to partition it into some number of contiguous subarrays such that each subarray, when considered as an array on its own, is good. As the answer may be large, output it modulo $1\\, 000\\, 003$ .

입력

The first line of input contains a single integer, $N$ .

The next line contains $N$ integers $a\_1, \dots , a\_N$ ( $1 ≤ a\_i ≤ N$ ).

출력

The number of ways to partition the array into good contiguous subarrays, modulo $1\\, 000\\, 003$ .

예제2

예제 1
입력
```
5
1 2 3 2 3
```
예상 출력
```
4
```
예제 2
입력
```
5
1 2 1 3 1
```
예상 출력
```
6
```