Problem G
Indistinguishable Sequences
SoCCat the Group Theorist is a very detail-oriented cat. Currently, SoCCat is researching a unique equivalence relation on sequences!
SoCCat defines a map $L: \bigcup _{i\in \mathbb N} \mathbb Z^ i \to \mathbb N$ which takes in a sequence $\mathbf s = (s_1, s_2, \ldots , s_ k)$ of integers and outputs the length of a longest (strictly) increasing subsequence of $\mathbf s$.
Two sequences $\mathbf s = (s_1, s_2, \ldots , s_ k)$ and $\mathbf t = (t_1, t_2, \ldots , t_ l)$ are said to be indistinguishable if and only if they belong to the same fiber of the map $L$ – in other words, if $L(s_1, s_2, \ldots , s_ k) = L(t_1, t_2, \ldots , t_ l)$. That is, two sequences are indistinguishable if and only if the lengths of their longest increasing subsequences are the same.
SoCCat considers a very natural question: given a sequence $\mathbf a = (a_1, a_2, \ldots , a_ n)$, how many subsequences of $\mathbf a$ are indistinguishable from the original sequence $\mathbf a$ itself?
SoCCat doesn’t believe that you can do it, so they simply gave you a random permutation $\mathbf a$ for you to tinker with.
Surprise SoCCat by outputting the answer modulo $1\, 000\, 003\, 233$!
Input
The first line of input contains an integer $n$, the length of the sequence ($1 \leq n \leq 100\, 000$).
The second line of input contains $n$ integers $a_1, a_2, \ldots , a_ n$, the integers in the permutation ($1 \leq a_ i \leq n$; $a_ i \neq a_ j$ if $i \neq j$). The permutation $\mathbf a$ is uniformly randomly generated from all $n!$ possible permutations.
Output
Output a single integer, the number of subsequences of $\mathbf a$ that are indistinguishable from $\mathbf a$. In other words, output the number of subsequences of $\mathbf a$ such that the length of their longest increasing subsequence is equal to the length of the longest increasing subsequence of $\mathbf a$.
As the answer can be very large, output the answer modulo $1\, 000\, 003\, 233$.
Notes
A sequence $\mathbf b$ is called a subsequence of another sequence $\mathbf a = (a_1,\ldots , a_ n)$ if there is a strictly increasing sequence of indices $i_1,\ldots , i_ p$ such that $\mathbf b = (a_{i_1},\ldots , a_{i_ p})$.
In the sample test case, we have $L(\mathbf a) = 2$, and any subsequences of $\mathbf a$ that belongs to the same fiber of $L$ as $\mathbf a$ must contain $a_2 = 1$, as well as either of $a_3$ or $a_4$ (or both).
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 1 3 2 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 2 4 8 7 3 9 5 6 1 10 |
84 |
