给定常数 $p,q$ 和序列 $a_{1\dots n}$，可以任意重排序列 $a$，最大化（或最小化）$p\cdot a_1+\sum_{i=2}^n a_i\cdot a_{i-1}+q\cdot a_n$。

这个问题是否存在多项式复杂度的做法？（最大化或最小化的做法均可）

自己有一个想法是当只有中间那一坨的时候似乎单峰是最优的，但加上两边之后似乎需要考虑更多的东西。