## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 it holds that ${a}_{i}={a}_{i-1}+1$.

Let's call $f\left(p\right)$ 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 $f\left(\left[1,2,3\right]\right)=1$, while $f\left(\left[3,1,2\right]\right)=2$ and $f\left(\left[3,2,1\right]\right)=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\left({p}^{\prime }\right)=k$.

Your task is to count for each $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$ to $n$ in arbitrary order. For example, $\left[2,3,1,5,4\right]$ is a permutation, but $\left[1,2,2\right]$ is not a permutation ($2$ appears twice in the array) and $\left[1,3,4\right]$ is also not a permutation ($n=3$ but there is $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\le n\le 2000$$10\le m\le {10}^{9}$) — the length of the permutation and the required modulo.

The second line contains $n$ distinct integers ${p}_{1},{p}_{2},\dots ,{p}_{n}$ ($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 $\left[1,3,4,2\right]$ are:

• $\left[1,2,3,4\right]$$f\left(\left[1,2,3,4\right]\right)=1$;
• $\left[1,2,4,3\right]$$f\left(\left[1,2,4,3\right]\right)=3$;
• $\left[1,3,2,4\right]$$f\left(\left[1,3,2,4\right]\right)=4$.

Thus our answer is $\left[1,0,1,1\right]$.

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

• $\left[1,2,3\right]$$f\left(\left[1,2,3\right]\right)=1$;
• $\left[1,3,2\right]$$f\left(\left[1,3,2\right]\right)=3$;
• $\left[2,1,3\right]$$f\left(\left[2,1,3\right]\right)=3$;
• $\left[2,3,1\right]$$f\left(\left[2,3,1\right]\right)=2$;
• $\left[3,1,2\right]$$f\left(\left[3,1,2\right]\right)=2$.

Thus our answer is $\left[1,2,2\right]$.