Chat

题意翻译

#### 题目描述： 有 $n$ 条信息，每次可以显示当前信息、前 $k$ 信息以及后 $k$ 条信息,如果当前信息以上或以下的信息数不足 $k$ ,则忽略不足。对于第 $i$ 个信息，可以通过其链接访问第 $a_i$ 个信息,可以访问当前信息的链接，但如果 $a_i=0$​​ 则不可访问。问最多可以访问多少条信息。 #### 输入格式： 输入共两行，第一行两个数 $n$ ​​ ($1 \le n \le 10^5$​) , $k$​ ($0 \le k \le n$​) ,分别表示信息总数和可以访问到前信息数或后信息数。第二行 $n$​ 个数，$a_i$​​​ 表示链接指向的信息。保证 $a_i<i$​​ 。 #### 输出格式 输出共一行，输出 $n$​ 个数，第 $i$ 个数表示从第 $i$ 号信息出发可以访问的最多信息数。 #### 样例解释： 对于第一个样例 $i=6$ ，先读6号信息，在读2号，然后1号，之后就没有链接了。 对于第一个样例 $i=6$ ，先是5、6、7，然后4、5、6，最后2、3、4，之后就没有链接了。

题目描述

There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued over 10 years ago. More formal, your message history is a sequence of messages ordered by time sent numbered from $ 1 $ to $ n $ where $ n $ is the total number of messages in the chat. Each message might contain a link to an earlier message which it is a reply to. When opening a message $ x $ or getting a link to it, the dialogue is shown in such a way that $ k $ previous messages, message $ x $ and $ k $ next messages are visible (with respect to message $ x $ ). In case there are less than $ k $ messages somewhere, they are yet all shown. Digging deep into your message history, you always read all visible messages and then go by the link in the current message $ x $ (if there is one) and continue reading in the same manner. Determine the number of messages you'll read if your start from message number $ t $ for all $ t $ from $ 1 $ to $ n $ . Calculate these numbers independently. If you start with message $ x $ , the initial configuration is $ x $ itself, $ k $ previous and $ k $ next messages. Messages read multiple times are considered as one.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1<=n<=10^{5} $ , $ 0<=k<=n $ ) — the total amount of messages and the number of previous and next messages visible. The second line features a sequence of integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}&lt;i $ ), where $ a_{i} $ denotes the $ i $ -th message link destination or zero, if there's no link from $ i $ . All messages are listed in chronological order. It's guaranteed that the link from message $ x $ goes to message with number strictly less than $ x $ .

输出格式

Print $ n $ integers with $ i $ -th denoting the number of distinct messages you can read starting from message $ i $ and traversing the links while possible.

输入输出样例

输入样例 #1

6 0
0 1 1 2 3 2

输出样例 #1

1 2 2 3 3 3 

输入样例 #2

10 1
0 1 0 3 4 5 2 3 7 0

输出样例 #2

2 3 3 4 5 6 6 6 8 2 

输入样例 #3

2 2
0 1

输出样例 #3

2 2 

说明

Consider $ i=6 $ in sample case one. You will read message $ 6 $ , then $ 2 $ , then $ 1 $ and then there will be no link to go. In the second sample case $ i=6 $ gives you messages $ 5,6,7 $ since $ k=1 $ , then $ 4,5,6 $ , then $ 2,3,4 $ and then the link sequence breaks. The number of distinct messages here is equal to $ 6 $ .