考虑这么证明：

将所有点绘制到一个坐标系上，若一个点被选择了，则我们称其为 $1$

结论：当我们有 $i < j,p_{i} > p_{j}$ 且 $i$ 被选择，则 $j$ 一定被选择

我们考虑这么证明：若 $j$ 被选择，则一定能够构造出一种新的方案使得其比当前方案更优

使用反证法，不妨设当前是最优答案且答案中存在两位置 $i,j$ 使得 $i<j,p_i>p_j$ 且 $i$ 选 $j$ 不选

不妨找到其中使得 $p_j-p_i$ 最小的 $i,j$ ，那么他就会满足

  • $p_i,p_j$ 中间没有比 $p_i$ 小且被选择的点
  • $p_i,p_j$ 中间没有比 $p_j$ 大且未被选择的点
  • 没有值在 $i，j$ 中间的元素

发现这样就将整个平面分割为了九个部分，我们分别将其称为

$$\begin{array}{a|a|a|a}\hline 1 & 2 & 3 \
\hline 4 & 5 & 6 \
\hline 7 & 8 & 9 \
\hline\end{array}$$
考虑让 $i,j$ 选择反转，计算每一部分的贡献

  • $(1,0),1 \rightarrow 0$
  • $(4,0),1 \rightarrow 0$
  • $(7,0),0 \rightarrow 0$
  • $(2,0),1 \rightarrow 0$
  • $(8,0),1 \rightarrow 1$
  • $(3,0),1 \rightarrow 1$
  • $(1,1),2 \rightarrow 2$
  • $(7,1),1 \rightarrow 1$
  • $(2,1),1 \rightarrow 1$
  • $(8,1),1 \rightarrow 0$
  • $(3,1),0 \rightarrow 0$
  • $(6,1),1 \rightarrow 0$
  • $(9,1),1 \rightarrow 1$

然后你发现每一位要么不变，要么变小，再加上本次操作后一定会 $-1$ ，于是我们就构造出了一种方案使得答案比当前答案更小，与假设相悖，所以得证

故最终答案中一定不存在 $i<j,p_i>p_j$ 且 $i$ 被选择的情况，故我们可以推出当 $i$ 被选择时，$j$ 一定选择

然后我们就可以拆贡献，考虑计算当一个点被选择时能够产生的贡献

此时以此为原点绘制平面直角坐标系，则第一象限的 $0$ 点会产生 $1$ 的贡献，第二象限的 $0$ 会产生 $-1$ 的贡献，第三象限的 $1$ 会产生 $-1$ 的贡献，第四象限的 $1$ 会产生 $1$ 的贡献

这样要同时讨论 $0,1$ 两种点，有点麻烦，不妨在一开始就加上每个点一二象限的贡献，转化成一三象限会产生 $1$ 的贡献，二四象限会产生 $-1$ 的贡献