雖然是基礎題還是放一下題解好了 www

題目一開始就提供每個 $p_i$ 了，所以沒必要依序計算 $q_2,q_3,\dots ,q_n$。以下提供兩種方法在 $O(n)$ 時間內算完 $q_i$ 們：

方法一：倒著算 + list

建立一條 list 像這樣：
$$-\mathrm{\infty }\rightleftarrows 1\rightleftarrows 2\rightleftarrows \dots \rightleftarrows n\rightleftarrows \mathrm{\infty }$$
讓這個 list 在計算 $q_i$ 時，裡面的元素除了 $\pm \mathrm{\infty }$ 以外，恰好就是 $p_1,\dots ,p_i$。這樣一來，想算 $q_i$，只要看 $p_i$ 左右兩邊和 $p_i$ 的距離就行了。算完 $q_i$ 後，把 $p_i$ 從這個 list 裡拔掉，就能在計算 $q_{i-1}$ 時保持上述提到的良好性質。

方法二：按 $p_i$ 遞增順序算 + stack

計算 $q_i$ 需要「滿足 $j<i$ 且 $p_j<p_i$ 的最大 $p_j$」以及「滿足 $j<i$ 且 $p_j>p_i$ 的最小 $p_j$」。我們維護一個 stack，保存 $(i,p_i)$ 數對們，且在任意時候 stack 裡的元素都是遞增的 (這裡遞增是指滿足偏序關係 $⪯$)。這樣一來，「滿足 $j<i$ 且 $p_j<p_i$ 的最大 $p_j$」們就能在 $O(n)$ 時間內算完。另外，我們還需要「滿足 $j<i$ 且 $p_j>p_i$ 的最小 $p_j$」們，而這可以用同樣的方法再做一次得到。但其實在維護上述的 stack 時，一旦有元素被 pop 掉，我們就知道那個被 pop 掉的 $i$ 的「滿足 $j<i$ 且 $p_j>p_i$ 的最小 $p_j$」是多少了，也就是可以只做一次單調 stack。

題目裡的故事好精彩。