Indistinguishable Sequences (Problem I, CS3233 Midterm Contest 2023, 2023)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement
> 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 \rightarrow \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\ \text{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
```
4
4 1 3 2
```
# Sample Output #1
```
6
```
# Sample Input #2
```
10
2 4 8 7 3 9 5 6 1 10
```
# Sample Output #2
```
84
```

Sample inputs:
4
4 1 3 2

10
2 4 8 7 3 9 5 6 1 10

Sample outputs:
6

84

# Solution Analysis

Let’s make a few observations. Since the test cases are random, we can generate them on our own to test whether our solution is fast enough.

First, we only need to consider elements which can be a part of some LIS (longest increasing subsequence). If an element $a_i$ is never part of any LIS, then deleting it will not affect the length of the LIS.

So, how can we determine whether an element could be part of a LIS? Let $\text{lis}_1(x)$ be the longest increasing subsequence on the prefix $[1, x]$ which ends at $x$, and $\text{lis}_2(x)$ be the longest increasing subsequence on the suffix $[x, n]$ which starts at $x$. We can compute both of these using the classic $O(n \log n)$ dynamic programming for LIS.

Suppose $L$ is the length of the LIS. An element $x$ can be part of some LIS if and only if $\text{lis}_1(x) + \text{lis}_2(x) = L + 1$ (since we count the index $x$ twice). If this equality is not satisfied, then that element can never be part of any LIS. After we have this, we delete all elements that are never part of any LIS, and now solve the problem on the reduced array $a'$. After we find the number of subsequences in $a'$, we can simply multiply that answer by $2^d$, where $d$ is the number of deleted elements.

Now, in the reduced array $a'$, how do we count the number of subsequences with the same LIS length? Notice that a LIS $(i_1, i_2, \ldots, i_L)$ have $\text{lis}_1(i_j) = j$. This motivates us to partition these elements into _levels_. Specifically, level $l$ will contain all elements with $\text{lis}_1(i) = l$. After we have these levels, we add edges between levels $l$ and $l + 1$ if $a_i < a_j$ where $i \in \text{level}(l)$ and $j \in \text{level}(l + 1)$.

On a random permutation with $n = 10^5$, it turns out that the size of $a'$ is at the very most only around $\approx 4000$. In addition, the maximum number of elements in a single level is at most around $\approx 20$. Hence, we can try to use a bitmask dynamic programming on the level graph structure.

Denote $\text{dp}(l, m)$ be the number of subsets of elements in levels $< l$, where the $b$-th bit of $m$ is 1 if and only if there exists a LIS ending at $\text{level}(l, b)$, and 0 otherwise. This state contains enough information, as a LIS must go through the levels sequentially in order $1, 2, \ldots, L$.

Now, suppose we fix $m$ in $\text{dp}(l, m)$. Which states $m'$ in $\text{dp}_{l+1}(m')$ can it transition to? Let $m''$ denote the bitmask of the maximal set of elements in $\text{level}(l + 1)$ where for every element $j \in m''$, exist $i \in m$ such that $a_i < a_j$. In other words, $m''$ is the maximal set of elements where we can potentially extend the LIS.

Now that we have $m''$, the possible transitions $m'$ are those that satisfy $m' \subseteq m''$. Furthermore, for each $m'$, we contribute by $\text{dp}(l, m) \times 2^{|\text{level}(l+1)| - |m'|}$, since we can leave the $|\text{level}(l+1)| - |m'|$ elements either in or out of the subsequence without affecting which elements have a LIS ending at them.

If we iterate the subsets $m' \subseteq m''$ naively, this runs in $O(3^k)$, where $k = |\text{level}(l + 1)|$ However, we can further optimize this with the sum over subsets dynamic programming to $O(k2^k)$. We can also optimize finding $m''$ by using bitmasks as an “adjacency matrix” (i.e. the $j$-th bit of $\text{adj}[i]$ is on iff there is an edge $(i, j)$) to $O(k2^k)$ as well. In total, we can transition from layer $l$ to $l + 1$ with time complexity $O(k2^k)$.

In practice, there are very few test cases where this solution is not fast enough. We checked over $10^6$ random permutations with $n = 10^5$ and only found 14 permutations with maximum layer size 24 or more. As there are only $\approx 200$ finalized test cases for this problem, the probability that this happens is very small.

**Challenge:** Can you prove the asymptotic bounds on the maximum number of elements in a single level? What about the total number of elements across all levels?

Special judge (C++ scorer):