每次询问，我们通过二分答案+前缀和加速，可以做到$O(\log n)$。总复杂度为$O(n\log n)$，空间复杂度$O(n)$。

具体操作是，当询问至$a_i$时，根据贪心的思想，显然有先将$a_{i-1}$、$a_{i+1}$合并至$a_i$，然后将$a_{i-2}$、$a_{i+2}$合并至$a_i$……以此类推。我们可以二分这个答案：当我们合并至$[i-k,i+k]$区间时，操作次数尚有富裕、但$[i-k-1,i+k+1]$时就操作次数不足了。然后我们可以$O(1)$求出剩余操作次数带来的收益。

在二分时，最关键的一点是如何$O(1)$计算出$[i-k,i+k]$区间的操作次数。这里可以用两个不同的前缀和数组进行数学转换求出，一个是$a_i$的前缀和，另一个是$a_i*i$的前缀和。注意我们计算右边和左边要分开来算（左边需要利用$a_i$的前缀和以及$a_i*(n-i+1)$的前缀和）。