P10174 "OICon-02" Great Segments

upd: The time limit has been changed to 400 ms. [Recommended enhanced version of the problem](https://www.luogu.com.cn/problem/P11291)

You are given a sequence $a$ of length $n$ with no repeated elements. For an interval $[l,r]$, we define it to be good if it satisfies the following conditions: 1. Define a sequence $b=\{ a_l,\max(a_l,a_{l+1}),\max(a_l,a_{l+1},a_{l+2}),\ ...\ ,\max(a_l,a_{l+1},\ ... \ ,a_r)\}$. After removing duplicates from this sequence, its length is at most $k$ and greater than $1$. 2. $\max(a_l,a_{l+1},\ ... \ ,a_r)=a_r$. Please solve the following problem: For each $i \ (1 \le i \le n)$, how many good intervals $[l,r]$ satisfy $l \le i \le r$.

The first line contains two integers $n,k$. The second line contains $n$ integers, where the $i$-th number denotes $a_i$.

Output $n$ lines, each containing one integer. The number on the $i$-th line denotes how many good intervals $[l,r]$ in the sequence satisfy $l \le i \le r$.

### Sample Explanation For sample $1$, the intervals that satisfy the conditions are: 1. $[1,2]$. 2. $[2,4]$. 3. $[3,4]$. Therefore, when $i=1,2,3,4$, the following intervals satisfy $l\leq i\leq r$ (by the interval indices above): 1. $1$ interval. 2. intervals $1,2$. 3. intervals $2,3$. 4. intervals $2,3$. ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | Special Property | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $n \le 200$ | $5$ | | $2$ | $n\leq 2000$ | $10$ | | $3$ | $\{a\}$ increasing | $10$ | | $4$ | $k\leq 5$ | $12$ | | $5$ | $k=n$ | $13$ | | $6$ | $n \le 3 \times 10^5$ | $20$ | | $7$ | No special restrictions | $30$ | For $100\%$ of the testdata: $1\leq k\leq n\leq 10^6$, $0\leq a_i\leq 10^9$. Translated by ChatGPT 5