本题存在 $\mathcal{O}(n)$ 的做法，出题人只是碍于 python 的运行速度限制才只把范围开到了 $100$。

---

你是一个 OIer，或者说，你以前是一个 OIer。在一次模拟赛中，你因为理解错了 $\text{D}$ 题题意而痛失了 $\text{100pts}$。模拟赛结束后，你十分的懊悔。  
你是一个好胜心很强的人，这一场模拟赛的失利让你无法接受。在学校里，你含着泪水，独自一个人坐在角落里，沉沉的睡了过去。   
再次睁开了眼，你发现你正处于机房之中。电脑左下角的时间显示着 $11:03$，这正是你今天开始做 $\text{D}$ 题的时间。   
怀着疑惑的心情，你打开了桌面上的 $\text{task.pdf}$。  
「终于，$\text{feluamn}$ 通过了蛮人族族长的考核。又是数个月穿梭于黑暗中，$\text{feluamn}$ 终于站在了光明之巅前。而黑暗之心蒙蔽了光明，通往光明之巅的路已经化为泥泞………」     
这正是今天的 $\text{D}$ 题。你试图继续往下看，却有着一股神秘的力量，阻挡你继续看下去。它告诉你，你没有必要，也不需要看这道题。   
「有一个 $n$ 个点的序列，有两种操作：  
1. 将点 $i$ 染色，代价为 $i$
2. 若点 $i$ 为特殊点，则可以将区间 $[i-k,i+k]$ 内的点染色，代价为 $i$ 
求将整个序列进行染色的最小代价。」  
“这道题很简单，你不需要去想这道题。”那股神秘的力量突然在你的脑子中发出了声音。   
“如果这道题中，若另一个特殊点 $i'$ 在被特殊点 $i$ 染色以后，还会继续以 $0$ 的代价，以相同的规则进行染色，那么答案会是什么样的呢？”