题解

思路

对固定的 $i$，只关心其他元素与 $P_i$ 的大小关系。

做法

若 $1<i<N$ 且 $P_{i-1},P_{i+1}$ 同时大于 $P_i$ 或同时小于 $P_i$，区间 $[i-1,i+1]$ 已经使 $P_i$ 不是中位数，答案为 $3$。否则从 $i$ 向左、向右分别扫描，找到最近的一对相邻元素，它们相对 $P_i$ 处在同一侧。在找到它们之前，大于和小于 $P_i$ 的元素交替出现，任何包含 $i$ 且不越过这对同侧元素的奇长区间，其他元素在 $P_i$ 两侧的数量都相等，中位数仍是 $P_i$。把该同侧对纳入区间，再在 $i$ 或相邻位置选取另一端使长度为奇数，就得到从这一方向越界的最短可行区间；左右候选取较小值，都不存在时答案为 $-1$。

对 $i=1$ 和 $i=N$ 单独向内扫描：在每个奇长前缀或后缀中统计小于、大于 $P_i$ 的元素个数，两者首次不等时即得最短答案。

复杂度

对内部位置，只有左右相邻元素分居 $P_i$ 两侧时才会继续扫描；将这些位置按下标排序，某一位置向右的扫描不会越过下一个这样的位置，向左同理，因而所有扫描的总长度为 $O(N)$，空间复杂度为 $O(N)$。