首先最优解怎么构造就不是很好想，构造最优解然后暴力算差不多就有个黄的难度，但这题 $n\leq 10^5$，还需要推式子算每个数的贡献，加上这部分感觉就有绿的难度了。