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

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

方法一：倒著算 + list

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

方法二：按 $\color{black}{p_i}$ 遞增順序算 + stack

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

題目裡的故事好精彩。