\(O(N\log N)\) 時間での解法を説明します．

(, ) を \(+1\), \(-1\) に対応させて，入力は \((+1, -1)\) の列として扱います．次のような問題になります．

各 \(i\) に対して \(L_i, R_i\) のどちらかを \(0\) に変更して，任意の prefix sum が非負かつ総和が \(0\) にせよ

まず，\(S_{L_i} = S_{R_i}\) であるような \((L_i, R_i)\) については貪欲な選択肢が決まります．

\(S_{L_i} = -1, S_{R_i}=1\) であるような \((L_i, R_i)\) については次のように考えます：

• \(S_{L_i} = -1\), \(S_{R_i} = 0\) で初期化しておく．このあと，次の操作を \(0\) 回または \(1\) 回行える：\(S_{L_i}, S_{R_i}\) の両方に \(+1\) する．

\(S_{L_i} = 1, S_{R_i}=-1\) であるような \((L_i, R_i)\) についても同様にします．次の問題に帰着できました：

数列 \(A\) と，いくつかの組 \((L_i, R_i)\) が与えられる．「\(A_{L_i}, A_{R_i}\) に \(+1\) する」という選択をいくつかの \(i\) に行って，\(A\) の prefix sum が非負かつ総和が \(0\) になるようにせよ．

これは，次のような貪欲アルゴリズムで判定可能です．

\(i=0, 1, 2, \ldots\) 順に prefix sum を計算していく．prefix sum が負になったら，\(L\leq i\) であるような未使用の組 \((L,R)\) であって \(R\) が最小のものを選んで操作を行う．操作が行えないならば No を出力する．