Here’s the English translation of the editorial:

For \(i=1\) and \(N\), the answer can be computed in \(O(N)\) time by a naive search.

Let’s consider \(i=2,3,\dots,N-1\). First, if the signs of \(P_{i-1}-P_i\) and \(P_{i+1}-P_i\) are the same, \((l,r)=(i-1,i+1)\) satisfies the conditions, so the answer is \(3\).

Next, let’s consider the case where the signs of \(P_{i-1}-P_i\) and \(P_{i+1}-P_i\) are different. Here, let \(R\) be the minimum value of \(j\ (i < j)\) such that the signs of \(P_{j+1}-P_i\) and \(P_{j}-P_i\) are the same, and \(L\) be the maximum value of \(j\ (j < i)\) such that the signs of \(P_{j-1}-P_i\) and \(P_{j}-P_i\) are the same.

Let’s consider whether \((l,r)\) satisfying \(L \leq l \leq i \leq r \leq R\) satisfies the conditions. For \((P_l,P_{l+1},\dots,P_{i-1},P_{i+1},\dots,P_r)\), from the way \(L\) and \(R\) are chosen, those greater than and less than \(P_i\) are alternately arranged. In particular, the numbers of those greater than and less than \(P_i\) are equal, so the median is \(P_i\). Therefore, \((l,r)\) satisfying the conditions (if it exists) must satisfy \(l < L\) or \(R < r\).

Let’s consider the case of \(l=L-1\). For \(r\), consider \(i\) or \(i+1\) for which \(r-l+1\) is odd. First, the difference between the number of those greater than \(P_i\) and the number of those less than \(P_i\) among \(P_{L},P_{L+1},\dots,P_{r}\) is \(1\), and there will be more of the smaller ones if \(P_L\) is less than \(P_i\) (and the opposite if \(P_L\) is greater than \(P_i\)). Thus, for the median of \((P_{L-1},P_{L},\dots,P_r)\) to be \(P_i\), the signs of \(P_{L-1}-P_i\) and \(P_{L}-P_i\) must be different, but from the way \(L\) is chosen, the signs are the same. Therefore, the median of \((P_{L-1},P_{L},\dots,P_r)\) is not \(P_i\), satisfying the condition. In particular, it is the smallest \(r-l+1\) among those satisfying \(l < L\).

A similar argument for \(r=R+1\) gives the smallest value of \(r-l+1\) when \(R < r\). These allow us to find the answer, so the problem is reduced to finding \(L,R\) for each \(i\). (As a note, if \(i=1\) or \(N\), we can’t, for example, choose \(r=i\) or \(i+1\) for which \(r-l+1\) is odd, so a naive search is necessary just for \(i=1\) and \(N\) as mentioned at the beginning.)

Let’s consider how to find \(L\) and \(R\) for each \(i=2,3,\dots,N-1\). This can be done in \(O(N\log N)\) time by updating the sign of \(P_{j}-P_i\) while looking at \(P_i\) in ascending order, and managing the positions where the signs are equal in adjacent parts using std::set or similar.

By the way, \(L\) and \(R\) need to be calculated only for \(i\) where the signs of \(P_{i-1}-P_i\) and \(P_{i+1}-P_i\) are different. Let such \(i\) be \(i_1,i_2,\dots,i_n\), and consider finding \(L\) and \(R\) for each of them by naive search. Let’s consider finding \(R\) for \(i_k\). Since the signs of \(P_{i_{k+1}-1}-P_{i_{k+1}}\) and \(P_{i_{k+1}+1}-P_{i_{k+1}}\) are different, either \(P_{i_{k+1}-1}-P_{i_k}\) and \(P_{i_{k+1}}-P_{i_k}\) or \(P_{i_{k+1}}-P_{i_k}\) and \(P_{i_{k+1}+1}-P_{i_k}\) have the same sign. Thus, \(R \leq i_{k+1}\), and a similar argument holds for \(L\), so the search for \(L\) and \(R\) can be done in \(O(i_{k+1}-i_{k-1})\) time. The sum of these is \(O(N)\), so it turns out that a naive search is sufficiently fast.