虽然这是一道思维&码量均普及-的题目，但是学数据结构学魔怔学而不思的你可以使用

暴力枚举+线段树or树状数组，以$O(nlogn)$的时间复杂度AC它

（真是有病，为什么不用亲爱的前缀和以$O(n)$时间通过要用这种东西）

咳，虽然但是，这种行为是很抽象的，明明只需要在$O(nlogn)$的排序完成后直接输出即可非要加个莫名其妙的暴力，初学者切莫模仿好好想题

最后，给出复杂度：三者时间均为$O(nlogn)$，空间：正解$O(n)$＝前缀和$O(n)$＝树状数组$O(n)＝$线段树$O(n)$

实际运行时间及实际占用空间：正解＜前缀和＜树状数组＜线段树