洛谷 P1667

这种奇怪的在数列上操作，看看在前缀和 / 差分数组上发生了什么事往往能发现新大陆。
考虑 \(a\) 的前缀和 \(S\)，不难发现操作 \([l,r]\) 就是交换 \(S_{l-1},S_r\)。
所以最终是要通过交换使得 \(S\) 单调递增，且都非负。
无解情况

• \(S\) 中出现相同的数
• \(S\) 中出现负数
• \(S_n\) 不是 \(S\) 中最大的

然后将 \(S\) 离散化后就变成了一个排列通过最少的交换次数变成目标排列的问题，此处目标排列为 \(1,2,\cdots,n\)。这是一个经典问题。