题目描述

给定一个长度为 $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$ 区间。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据：$1\leq k\leq n\leq 10^6$，$0\leq a_i\leq 10^9$。