\(i=1,N\) に対しては愚直に調べることで \(O(N)\) 時間で計算できます。

\(i=2,3,\dots,N-1\) に対して考えます。まず \(P_{i-1}-P_i, P_{i+1}-P_i\) の符号が同じである場合、 \((l,r)=(i-1,i+1)\) が条件を満たすので答えは \(3\) です。

次に \(P_{i-1}-P_i, P_{i+1}-P_i\) の符号が異なる場合を考えます。ここで、 \(P_{j+1}-P_i, P_{j}-P_i\) の符号が同じであるような \(j\ (i < j)\) の最小値を \(R\) 、 \(P_{j-1}-P_i, P_{j}-P_i\) の符号が同じであるような \(j\ (j < i)\) の最大値を \(L\) とします。

\(L \leq l \leq i \leq r \leq R\) を満たす \((l,r)\) が条件を満たすかについて考えます。 \((P_l,P_{l+1},\dots,P_{i-1},P_{i+1},\dots,P_r)\) について、 \(L,R\) の取り方から \(P_i\) より大きいもの、小さいものが交互に並んでいます。特に \(P_i\) より大きいもの、小さいものの個数は等しく、中央値は \(P_i\) になります。よって、条件を満たす \((l,r)\) は（存在するならば）\(l < L, R < r\) のいずれかを満たす必要があります。

では \(l=L-1\) のケースについて考えてみます。 \(r\) としては \(i,i+1\) のうち、 \(r-l+1\) が奇数になるようなものを考えます。 まず \(P_{L},P_{L+1},\dots,P_{r}\) のうち、 \(P_i\) より大きいものの個数と \(P_i\) より小さいものの個数の差は \(1\) であり、 \(P_L\) が \(P_i\) より小さい場合は小さいほうが多くなります（ \(P_L\) が \(P_i\) より大きいなら逆）。このため、 \((P_{L-1},P_{L},\dots,P_r)\) の中央値が \(P_i\) になるには \(P_{L-1}-P_i,P_{L}-P_i\) の符号が異なる必要がありますが、 \(L\) の取り方から符号は同じです。以上より \((P_{L-1},P_{L},\dots,P_r)\) の中央値は \(P_i\) ではなく条件を満たします。特に、 \(l < L\) を満たすものの中では \(r-l+1\) が最小です。

\(r=R+1\) に対しても同様の議論から、 \(R < r\) を満たすものの中で \(r-l+1\) が最小のものが取れます。これにより答えが求められるので、問題は各 \(i\) に対して \(L,R\) を求めることに帰着されます。（注意点として、 \(i=1,N\) の場合は \(r=i,i+1\) のうち \(r-l+1\) が奇数になる方、などという取り方ができません。このため \(i=1,N\) だけ最初に述べたように愚直に調べることが必要になります）

各 \(i=2,3,\dots,N-1\) に対して \(L,R\) の求め方を考えます。これは \(P_i\) を昇順にみていくことで \(P_{j}-P_i\) の符号を更新し、さらに隣接している部分で符号が等しくなっている位置を std::set などで管理することで \(O(N\log N)\) 時間で求めることができます。

ところで、 \(L,R\) を計算する必要があるのは \(P_{i-1}-P_i,P_{i+1}-P_i\) の符号が異なるような \(i\) に対してだけです。このような \(i\) を \(i_1,i_2,\dots,i_n\) とし、それぞれについて \(L,R\) を愚直な探索により求めることを考えます。 \(i_k\) に対して \(R\) を求めることを考えましょう。 \(P_{i_{k+1}-1}-P_{i_{k+1}}, P_{i_{k+1}+1}-P_{i_{k+1}}\) の符号が異なることから、 \(P_{i_{k+1}-1}-P_{i_k}, P_{i_{k+1}}-P_{i_k}\) か \(P_{i_{k+1}}-P_{i_k},P_{i_{k+1}+1}-P_{i_k}\) のどちらかは符号が等しくなります。よって \(R \leq i_{k+1}\) であり、 \(L\) についても同様に考えると \(L,R\) の探索は \(O(i_{k+1}-i_{k-1})\) 時間で行えます。これらの和は \(O(N)\) であるため、実は愚直な探索でも十分高速であることが分かります。