一个显然的结论是:相邻两个下标中,至多一个下标进行过操作.
 于是我们可以把所有操作过的 $i$ 分为若干个极长段,每个极长段为一个公差为 $2$ 的等差数列;不同极长段之间至少间隔两个数,且相互之间独立.
 考虑 $p$ 和目标的升序排列中不变的位置,显然不变的位置只能是操作过的 $i$,以及不同连续段之间间隔的位置.因此根据不变的位置我们可以贪心地划分出连续段,如果出现矛盾则说明无解.
 现在考虑一个连续段内如何判断是否可行.
 注意到,每个奇数位上的数一定只会往一个方向运动,因此向同一个方向运动的数的相对位置不变.
 证明大概就是,向左移动的数在不超过前面的数的情况下一定可以不断向左,向右移动的数在不超过前面的数的情况下一定可以不断向右.
 总结一下,如果这个排列合法,则可以:
 贪心地根据不变的位置将排列划分成若干个连续段.
 每个段的值域恰好等于下标.
 int n, p[N];
 else L = p[i];
 else R = p[i];
 在此浏览器中保存我的名字,电邮和网站.