• 数形结合，定义域值域互换，数据随机题。

考虑放到二维平面上刻画该问题，那么就是有若干点 $(i,a_i)$，我们要求对于任意横坐标 $[l,r]$ 的最小子矩形而言，就要求 $(l,a_l),(r,a_r)$ 这两个点至少一个在矩形的四个角上。先不管数据随机的限制，用记忆化搜索的思路我们思考如何生成一个合法序列，记当前还未填写的数是集合 $S$，当前仍未填写的区间是 $[L,R]$，那么你每次是将 $S_{\max},S_{\min}$ 的两者之一放到端点上，那么 $[L,R]$ 就缩减为 $[L,R-1]/[L+1,R]$，而 $S$ 由于是删除最小或者最大值那么显然是连续的。也就是说对于大正方形你每次会删除一个 $\texttt{L}$ 形。因此有一个 $\mathcal O(n^3)$ 的状态设计就是，$f_{l,r,x}$ 为当前为 $[l,r]$ 的区间时 $[x,x+r-l]$ 还未填写，这些所有序列与原序列的保留最大值。

注意到数据随机，猜测答案很大，事实上保留的数的级别是 $\mathcal O(\sqrt n)$。考虑“保留”是什么意思，对于 $i$ 有四个方向的正方形其边长为 $d$，那么就有 $(i,a_i)$ 往四个方向的正方形。我们考察被保留下来的 $k$ 个点，那么就是要对于所有被保留的点，考虑一个严格单调的序列 $d$ 以及方向 $dir$ 来刻画其正方形。我们要求对于这 $k$ 个正方形是两两严格包含的关系。

那么这样就很好做了。我们放到一个正方形上去分析，但之前我们宣称了答案的量级很小，原本是 $f_{i,dir,j}$ 表示 $(i,a_i)$ 的第 $dir$ 方向的正方形边长为 $j$ 时最多包含多少个子正方形，显然其具有单调性，因此考虑定义域值域互换。可以更改为 $g_{i,dir,j}$ 表示 $(i,a_i)$ 的 $dir$ 方向正方形，如果包含 $\ge j$ 个子正方形，其要求最小的边长是 $g_{i,dir,j}$。考虑对于 $j$ 维度进行扫描线，因为转移就是 $g_{*,j}$ 由 $g_{*,j-1}$ 来转移。然后这就是一个二维平面的问题，可以用对角线拆成两个三角形，树状数组维护二维偏序做一下。时间复杂度 $\mathcal O(n\sqrt n\log n)$。$\mathcal O(\sqrt n)$ 的分析来自于随机序列的最长上升子序列期望长度。

只需要跑 $8$ 次二维偏序就行了。优美的写法是每次旋转一下坐标系，但我不会。

提交记录。

考虑一个重排后的排列应该长什么样子，不妨固定住一对 $l,r$ 满足 $l<r$，要求就是不能同时存在 $l<k_1,k_2<r$ 使得 $p_{k_1}<\min(p_l,p_r)$ 和 $p_{k_2}>\max(p_l,p_r)$，换句话说也就是 $p_l,p_r$ 里至少要有一个是区间 $[l,r]$ 的最值。

换个角度看，假设一开始有 $1$ 到 $n$ 这些数，要把它们排成一个合法的排列，就要求每次必须把当前的最大值/最小值插到当前没被插入数的最靠前/最靠后的位置，排列合法当且仅当每一步都满足这个条件，而我们希望最大化插入过程中与原排列重合的位置数量。

然后就有个暴力的区间 dp 做法，可以设 $f_{l,r,x}$ 表示区间 $[l,r]$ 以外的部分已经填完，当前剩下的最大值为 $x$ 时区间内最大的重合位置数量，转移直接枚举在左右端点填最大/最小值四种情况是 $O(1)$ 的，所以得到了一个 $O(n^3)$ 的做法，可以通过 $70$ 分。

继续优化，考虑在二维平面的角度上看这个问题。因为新排列一个区间内的数在值域上肯定是连续的，把 $p_i$ 看成平面上的点 $(i,p_i)$，那么对于 $p$ 的一个区间 $[l,r]$ 能包住区间内的点的最小矩形就是 $x\in[l,r],y\in[d,u]$ 的这么一个矩形，其中 $d,u$ 分别是区间内的最小值和最大值。而因为每次只会填左右端点的一个最值， 那么填完之后剩下的子区间对应的矩形 $u,d$ 的变化量只有 $1$，也就是说每次会删去当前矩形边缘的一个 L 形。而初始时整个排列对应的矩形显然是 $x\in[1,n],y\in[1,n]$ 这么个大正方形，所以每个区间对应的矩形也都应当是个正方形。

对于一个 $p_i$ 来说，它与新的排列重合相当于是 $(i,p_i)$ 作为了某个区间对应正方形的四个顶点之一。考虑到所有以 $(i,p_i)$ 为顶点的正方形其对应的另一个顶点坐标都形如 $(i\pm len,p_i\pm len)$（正负号对应了四个方向），对每个 $(i,p_i)$ 都把这种正方形找出来，发现问题其实可以转化为：平面内有 $O(n^2)$ 个正方形，你需要选择尽可能多的正方形使得它们之间是严格包含的关系。这是因为对于选出来的这些正方形，因为只有包含关系，我们一定能构造出一组方案使得这些正方形同时出现过，每出现过一个就多一个位置不需要交换，所以答案就是 $n$ 减去最多选出的正方形个数。

设 $f_{i,j,dir}$ 表示 $(i,p_i)$ 向 $dir$ 方向延伸出的长度为 $j$ 的正方形（$dir\in\{0,1,2,3\}$），最多包含几个其它的正方形，转移考虑从满足 $k<i\And l< j$ 的 $f_{k,l,*}$ 转移，分类讨论不同方向之间的正方形成包含关系的条件，能够把转移限制表示成二维偏序，这个 dp 能够做到 $O(n^2\log n)$，但是本身 $n$ 就 $8000$ 而且常数太大了肯定过不去。

发现题目里还有随机排列的条件没有用，可以感受到随机排列的情况下能够选出的正方形不会太多，改成设 $f_{i,j,dir}$ 表示 $(i,p_i)$ 向 $dir$ 方向的正方形要包含 $j$ 个其它的正方形，最小的边长是多少，转移同样可以分类讨论变成二维偏序。一个结论就是 $j$ 这一维的大小是 $O(\sqrt n)$ 级别的，大概就是与随机排列的 LIS 长度是同阶的，所以这样就能做到 $O(n\sqrt n\log n)$，可以通过。

这里补充下具体怎么把转移写成二维偏序，假设我们现在要对 $f_{i,j,0}$ 进行转移，考虑之前 $j'=j-1$ 时的一个矩形 $x\in[l,r],y\in[d,u]$，那么首先要满足的条件就是 $i<l$ 且 $p_i<d$，转移过来后正方形的长度当 $d-p_i\le l-i$ 也就是 $d-l\le p_i-i$ 的时候是 $r-i$，否则是 $u-p_i$。注意到，如果满足 $i<l$ 那么当 $d-p_i> l-i$ 时就天然满足了 $p_i<d$，同理如果满足 $p_i<d$ 那么当 $d-p_i\le l-i$ 的时候也天然满足了 $i<l$，因此转移的贡献也是可以确定住的，跑两遍二维偏序即可。对于 $dir$ 为其它数的情况可以类似的讨论处理，这样对每层 $j$ 转移是跑八遍二维偏序，比较唐，但是我也不会其它更好的做法。

代码是贺的，不放了。