무거운 정수와 가벼운 정수

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

요약

배열을 연속된 구간으로 나눌 때, 각 구간 안에서 한 번만 나온 값과 두 번 이상 나온 값이 번갈아 나오는 분할의 수를 1,000,003으로 나눈 나머지로 구합니다.

문제

양의 정수로만 이루어진 배열에서, 배열 안에 두 번 이상 나타나는 정수를 무거운 정수라고 한다. 그렇지 않은 정수는 가벼운 정수라고 한다.

배열의 정수들이 가벼운 정수와 무거운 정수를 번갈아 가며 나타나면 그 배열은 좋은 배열이다.

배열 $a_1, \dots, a_N$ 이 주어진다. 연속된 부분 배열로 나누는 방법 중, 나뉜 각 부분 배열을 하나의 배열로 보았을 때 모두 좋은 배열이 되도록 하는 방법의 수를 세어라. 답이 클 수 있으므로 1,000,003으로 나눈 나머지를 출력한다.

첫째 줄에 정수 $N$ 이 주어진다.

둘째 줄에 정수 $a_1, \dots, a_N$ ( $1 \le a_i \le N$ )이 $N$ 개 주어진다.

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