[Solution] Doping Codeforces Solution

G. Doping

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

We call an array 𝑎$a$ of length 𝑛$n$ fancy if for each 1<𝑖≤𝑛$1<i\le n$ it holds that 𝑎𝑖=𝑎𝑖−1+1$a_i=a_{i-1}+1$.

Let's call 𝑓(𝑝)$f(p)$ applied to a permutation†${}^{†}$ of length 𝑛$n$ as the minimum number of subarrays it can be partitioned such that each one of them is fancy. For example 𝑓([1,2,3])=1$f([1,2,3])=1$, while 𝑓([3,1,2])=2$f([3,1,2])=2$ and 𝑓([3,2,1])=3$f([3,2,1])=3$.

Given 𝑛$n$ and a permutation 𝑝$p$ of length 𝑛$n$, we define a permutation 𝑝′$p^{\prime }$ of length 𝑛$n$ to be 𝑘$k$-special if and only if:

• 𝑝′$p^{\prime }$ is lexicographically smaller‡${}^{‡}$ than 𝑝$p$, and
• 𝑓(𝑝′)=𝑘$f(p^{\prime })=k$.

Your task is to count for each 1≤𝑘≤𝑛$1\le k\le n$ the number of 𝑘$k$-special permutations modulo 𝑚$m$.

†${}^{†}$ A permutation is an array consisting of 𝑛$n$ distinct integers from 1$1$ to 𝑛$n$ in arbitrary order. For example, [2,3,1,5,4]$[2,3,1,5,4]$ is a permutation, but [1,2,2]$[1,2,2]$ is not a permutation (2$2$ appears twice in the array) and [1,3,4]$[1,3,4]$ is also not a permutation (𝑛=3$n=3$ but there is 4$4$ in the array).

‡${}^{‡}$ A permutation 𝑎$a$ of length 𝑛$n$ is lexicographically smaller than a permutation 𝑏$b$ of length 𝑛$n$ if and only if the following holds: in the first position where 𝑎$a$ and 𝑏$b$ differ, the permutation 𝑎$a$ has a smaller element than the corresponding element in 𝑏$b$.

Input

The first line contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤2000$1\le n\le 2000$, 10≤𝑚≤109$10\le m\le {10}^9$) — the length of the permutation and the required modulo.

The second line contains 𝑛$n$ distinct integers 𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$ (1≤𝑝𝑖≤𝑛$1\le p_i\le n$) — the permutation 𝑝$p$.

Output

Print 𝑛$n$ integers, where the 𝑘$k$-th integer is the number of 𝑘$k$-special permutations modulo 𝑚$m$.

Note

In the first example, the permutations that are lexicographically smaller than [1,3,4,2]$[1,3,4,2]$ are:

• [1,2,3,4]$[1,2,3,4]$, 𝑓([1,2,3,4])=1$f([1,2,3,4])=1$;
• [1,2,4,3]$[1,2,4,3]$, 𝑓([1,2,4,3])=3$f([1,2,4,3])=3$;
• [1,3,2,4]$[1,3,2,4]$, 𝑓([1,3,2,4])=4$f([1,3,2,4])=4$.

Thus our answer is [1,0,1,1]$[1,0,1,1]$.

In the second example, the permutations that are lexicographically smaller than [3,2,1]$[3,2,1]$ are:

• [1,2,3]$[1,2,3]$, 𝑓([1,2,3])=1$f([1,2,3])=1$;
• [1,3,2]$[1,3,2]$, 𝑓([1,3,2])=3$f([1,3,2])=3$;
• [2,1,3]$[2,1,3]$, 𝑓([2,1,3])=3$f([2,1,3])=3$;
• [2,3,1]$[2,3,1]$, 𝑓([2,3,1])=2$f([2,3,1])=2$;
• [3,1,2]$[3,1,2]$, 𝑓([3,1,2])=2$f([3,1,2])=2$.

Thus our answer is [1,2,2]$[1,2,2]$.