32418번 - Heavy Light Decomposition 서브태스크다국어

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$.