這天，一款全新的妹妹虛擬實境遊戲即將發售，身為這類遊戲的愛好者—— 小 Y 為了搶先體驗，他現在身處在一個很長的隊伍中，漫長的等待時間使
他非常無聊，所以他決定開始觀察隊伍的排隊現象。
小 Y 觀察到隊伍內總共有 N 個人，一開始隊伍是在筆直的數線上的，第 i 個人的座標為 i。小 Y 也知道自己是這隻隊伍的第 Q + 1 個人，所以他很
在意前 Q 個人依序買到遊戲後，隊伍會發生什麼事。
因此，小 Y 接下來會觀察 Q 次事件，第 i 次事件排在隊伍最前面的人，也就是第 i 個人， 就會買到遊戲，並離開隊伍，自此這個人的位置便會出現空
格，此時隊伍可能會開始移動。
不過常常會有討厭的人待在原地不動（像是滑手機之類的），導致後面的人會因為察覺不到隊伍有移動而無法前進，小 Y 發現對於第 i 次事件，有往前
移動的人是還待在原隊伍的前 ki 位 （也就是第 i + 1 ∼ i + ki 個人），這 ki 位會不受影響地依序直接移動到前 ki 個位置，也就是座標 1 ∼ ki。
小 Y 已經把所有事件的 ki 都紀錄下來了，你可以告訴他，對於每次事件，隊伍內所有人 （包含該次事件買到遊戲的人）移動的距離總和是多少呢？當
然，我們假設每次事件只有買到遊戲的人和待在原隊伍的前 ki 個人會做移動，且任何人都只會在事件發生時移動。
輸入的第一行有兩個正整數 N, Q，代表隊伍的人數、小 Y 前面排了多少人。 第二行有 Q 個以空格分開的整數 k1, k2, · · · , kQ，代表每次事件，往前移動的人是還待在原隊伍的前 ki 位，若 ki = 0 代表此次事件除了買遊戲的人以外，沒有其他的人移動。
1. 1 ≤ N ≤ 109
2. 1 ≤ Q ≤ min(N − 1, 106 )
3. 0 ≤ ki ≤ N − i
輸出只有一行 Q 個數字 d1, d2, · · · , dQ，代表第 i 次事件中，所有人移動的距離總和是 di。
10 5 3 4 2 5 3
3 6 2 15 3
8 6 3 1 2 1 0 0
3 1 5 1 0 5
1000000000 7 100 1000 10000 8787 888777 98765 123456
100 1901 28002 8787 4405105 98765 148148
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||