{"raw_statement":[{"iden":"background","content":"upd：时间限制改为 400ms\n\n[加强版题目推荐](https://www.luogu.com.cn/problem/P11291)"},{"iden":"statement","content":"给定一个长度为 $n$ 的无重复元素序列 $a$。\n\n对于一个区间 $[l,r]$，我们定义它是好的，有以下条件：\n\n1. 定义一个序列 $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$；\n2. $\\max(a_l,a_{l+1},\\ ... \\ ,a_r)=a_r$。\n\n请你解决这样一个问题：对于每一个 $i \\ (1 \\le i \\le n)$，有多少个好的区间 $[l,r]$ 满足 $l \\le i \\le r$。"},{"iden":"input","content":"第一行两个整数 $n,k$。\n\n第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。"},{"iden":"output","content":"$n$ 行，每行一个整数，第 $i$ 行的数表示序列中有多少个好的区间 $[l,r]$ 满足 $l \\le i \\le r$。"},{"iden":"note","content":"### 样例解释\n\n对于样例 $1$，满足条件的区间有：\n\n1. $[1,2]$；\n2. $[2,4]$；\n3. $[3,4]$。\n\n故当 $i=1,2,3,4$ 时，分别有以下区间满足 $l\\leq i\\leq r$（根据上述的区间编号）：\n\n1. $1$ 区间；\n2. $1,2$ 区间；\n3. $2,3$ 区间；\n4. $2,3$ 区间。\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n| $\\text{Subtask}$ | 特殊性质 | $\\text{Score}$ |\n| :----------: | :----------: | :----------: |\n| $1$ | $n \\le 200$ | $5$ |\n| $2$ | $n\\leq 2000$ | $10$ | \n| $3$ | $\\{a\\}$ 递增 | $10$ |\n| $4$ | $k\\leq 5$ | $12$ |\n| $5$ | $k=n$ | $13$ |\n| $6$ | $n \\le 3 \\times 10^5$ | $20$ |\n| $7$ | 无特殊限制 | $30$ |\n\n对于 $100\\%$ 的数据：$1\\leq k\\leq n\\leq 10^6$，$0\\leq a_i\\leq 10^9$。"}],"translated_statement":null,"sample_group":[["4 2\n1 3 2 4","1\n2\n2\n2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}