「OICon-02」Great Segments

upd：时间限制改为 400ms [加强版题目推荐](https://www.luogu.com.cn/problem/P11291)

给定一个长度为 $n$ 的无重复元素序列 $a$。 对于一个区间 $[l,r]$，我们定义它是好的，有以下条件： 1. 定义一个序列 $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)\}$，将该序列进行去重操作后，该序列的长度不超过 $k$ 且大于 $1$； 2. $\max(a_l,a_{l+1},\ ... \ ,a_r)=a_r$。 请你解决这样一个问题：对于每一个 $i \ (1 \le i \le n)$，有多少个好的区间 $[l,r]$ 满足 $l \le i \le r$。

第一行两个整数 $n,k$。 第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

$n$ 行，每行一个整数，第 $i$ 行的数表示序列中有多少个好的区间 $[l,r]$ 满足 $l \le i \le r$。

4 2
1 3 2 4

1
2
2
2

### 样例解释 对于样例 $1$，满足条件的区间有： 1. $[1,2]$； 2. $[2,4]$； 3. $[3,4]$。 故当 $i=1,2,3,4$ 时，分别有以下区间满足 $l\leq i\leq r$（根据上述的区间编号）： 1. $1$ 区间； 2. $1,2$ 区间； 3. $2,3$ 区间； 4. $2,3$ 区间。 ### 数据范围 **本题采用捆绑测试。** | $\text{Subtask}$ | 特殊性质 | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $n \le 200$ | $5$ | | $2$ | $n\leq 2000$ | $10$ | | $3$ | $\{a\}$ 递增 | $10$ | | $4$ | $k\leq 5$ | $12$ | | $5$ | $k=n$ | $13$ | | $6$ | $n \le 3 \times 10^5$ | $20$ | | $7$ | 无特殊限制 | $30$ | 对于 $100\%$ 的数据：$1\leq k\leq n\leq 10^6$，$0\leq a_i\leq 10^9$。