P3759 [TJOI2017] 不勤劳的图书管理员

加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。 他的任务是把书排成有序的，所以无序的书让他产生厌烦。 两本乱序的书会让小豆产生这两本书页数的和的厌烦度。 现在有 $n$ 本被打乱顺序的书，在接下来 $m$ 天中每天都会因为读者的阅览导致书籍顺序改变位置。 因为小豆被要求在接下来的 $m$ 天中至少要整理一次图书。 小豆想知道，如果他前 $i$ 天不去整理，第 $i$ 天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。

无

无

#### 数据规模与约定 - 对于 $20\%$ 的数据，$1\le a_i,x_j,y_j\le n \le 5\times 10^3$，$1\le m\le 5\times 10^3$， $1\le v_i\le10^5$。 - 对于 $100\%$ 的数据，$1\le a_i,x_j,y_j\le n\le 5\times 10^4$，$1\le m\le 5\times 10^4$，$1\le v_i\le 10^5$。