思维训练懒得写代码了，感觉这种题还是思维为重。
我们显然需要考察两个东西：
- 最终序列会变成啥样。
- 每次是如何一步一步变成最终序列的。
我们先想第一个问题，显然，最终的 \(p\) 一定会是最大的那个 \(a_x\) 的 \(x\)，因为将最高的改高一定不优。
优化一下更改操作，每次将一段单调不降的前缀和单调不升的后缀干掉，那么只需要处理中间的值即可。
此时部分分就起到了很关键的作用，考察第二个问题，同样可以拆分成两个问题：
- 确定 \(j\) 的情况下，如何选择 \(i, k\)。
- 如何确定选 \(j\) 的顺序。
显然，考察完第一步是不会影响到第二步的决策的，此时第一步是简单的，选择 \(j\) 两边次小的 \(a_i, a_k\) 所对应的 \(i, k\) 即可。
本题的难点就在考察第二步。
我们仔细思考，发现一定先操作最小值，再操作最大值，否则 \(a_i, a_k\) 就可能会变得更大，影响到了整体的决策。一步一步想到这里，接下来的部分就是简单的了，我们只需要再次考察最小值之间的操作顺序即可，发现为了使得 \(a_i, a_k\) 尽量的小，我们一定是先操作最旁边的两个，中间的随便操作贡献就是一样的，只需要分类讨论一下是先操作左边还是右边即可。
具体过程可以用 set 和主席树维护。