Background

upd: The time limit has been changed to 400 ms.

Recommended enhanced version of the problem

Problem Description

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$.

Input Format

The first line contains two integers $n,k$.

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

Output Format

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$.

4 2
1 3 2 4

1
2
2
2

Hint

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.

For $100\%$ of the testdata: $1\leq k\leq n\leq 10^6$, $0\leq a_i\leq 10^9$.

Translated by ChatGPT 5