クエリを $A$ の各要素について $+1$ 倍するか $-1$ 倍するかを選択して任意の prefix sum を $0$ 以上にする問題と思います．
まず $DP[i][j] := $ $A_i$ まで $j$ 個 $-1$ 倍したときの $A_1 + A_2 + \cdots + A_i$ としてありうる最大値 (不可能なら $- \infty$) と定義して $O(N^2)$ 解法を得ます．

上の DP の $i$ を固定したとき $j$ に関する差分を管理することを考えると以下の $O(N \log N)$ アルゴリズムを得ます．以降アルゴリズム $X$ と呼びます．

大きい方の値を取り出してくれる priority_queue を用意する．$i = 1, 2, \cdots, N$ の順に以下を行う．

• priority_queue に $A_i$ を push する．
• $S = A_1 + A_2 + \cdots + A_i$ として priority_queue に入っている要素の総和が $\frac{S}{2}$ 以下になるまで pop する．(ここの $S$ の計算では $A_i$ は正として扱う．)

$i = N$ を終えた時点での priority_queue のサイズが求めるべき答えである．

実は，アルゴリズム $X$ の実行結果は以下のアルゴリズム $Y$ と同じになります．

値が小さい順 (タイブレークは index が大きい順) に $A_i$ について以下を行う．

• $A_i$ を $-1$ 倍する．
• もし $A_1 + A_2 + \cdots + A_j < 0$ なる $j$ が存在するなら $A_i$ を $+1$ 倍に戻す．

全ての $A_i$ について行った後，$-1$ 倍されている $A_i$ の個数が求めるべき答えである．

アルゴリズム $Y$ は lazy segment tree などを用いることで $O(N \log N)$ となります．これを高速化すると，適切な前準備のもとでアルゴリズム $Y$ の結果をクエリあたり $O(\max(A_i)\log N)$ などで求めることができ，満点が得られます．
実装例

その部分の説明は省略して，このユーザ解説ではアルゴリズム $X$ の実行結果がアルゴリズム $Y$ と同じになることを示します．長さ $N$ に関する帰納法で考えます．
アルゴリズム $X$ について，$(A_i, -i)$ の pair の形で要素を管理しているとして結果は変わりません．アルゴリズム $Y$ について，$A_1 + A_2 + \cdots + A_j < 0$ なる $j$ が存在することを違反していると呼びます．

$Y$ で $A_j$ を $-1$ 倍したとします．まず，$k < j$ かつ既に $Y$ で見た $A_k$ について $A_k < A_j$ が成立します．
$A_k$ を $-1$ 倍しなかった場合，それは $A_j$ より前で違反しています．もし，$A_j$ 以降で違反している場合，$A_j$ を $-1$ 倍することと矛盾するためです．よって，$A_k$ を $-1$ 倍している場合，$A := A[1, j - 1]$ としても $-1$ 倍しています．
また $A := A[1, j - 1]$ として $X$ を行った場合，最終的な priorirty_queue に $A_j$ 未満が入っているかは $Y$ で $A_j$ を見る前と同じです．($N$ に関する帰納法より)
これより $X$ を $i = j$ まで行った後の priority_queue において $A_j$ は入っています．priority_queue から $i = j$ で $(A_j, -j)$ を pop するとしたとき，その直前の $A_1, A_2, \cdots, A_{j - 1}$ における状況は $A := A[1, j - 1]$ として $Y$ を行った場合と同じになるためです．

加えて，$A_k$ $(k > j)$ で既に $Y$ で見たものについては $A_k \leq A_j$ が成立しています．よってこの中に選択しなかったものがあれば矛盾です．$A_k$ が $-1$ 倍できないという仮定のもとで $A_k$ より左側にあり，かつ $A_k$ 以上の要素を $-1$ 倍すれば当然矛盾するためです．

これより $X$ の $i = i' (> j)$ で $(A_j, -j)$ が pop されてるとすると，$(A_j, -j)$ を pop する直前の priority_queue の中身は {$A[1, j - 1]$ で $X$ をした時の最終的な中身} + {$A_j$} + {$A[j + 1, i']$ で $A_j$ 以下のものの一部} になっているが，最後の「一部」を「全部」にしても $Y$ で $A_j$ を $-1$ 倍にしているので priority_queue の中身は $\frac{S}{2}$ 以下となり矛盾します．

以上より $A_j$ は $X$ で pop されません．これより「 $Y$ で $A_j$ を $-1$ 倍することを選択 $\rightarrow$ $X$ で採用される」がいえました．

$Y$ で $A_j$ を $+1$ 倍したとします．$-1$ 倍しないということはどこかで違反しているが，そのような $i$ で一番小さいものを $i'$ とします．
$A := A[1, i' - 1]$ としての帰納法と上の議論を考えると，$X$ で $i = i' - 1$ まで操作した後の priority_queue の中身は {$A[1, j - 1]$ で $X$ をした時の最終的な中身} + {$A_j$} + {$A[j + 1, i' - 1]$ で $A_j$ 以下のものの全部} を含みます．
ここで $A_i'$ を考えると $Y$ で $A_j$ を $-1$ 倍しなかったことより上の priority_queue から pop しなければならないです．$(A_j, -j)$ の直前まで pop すると，上の 「を含む」 の直前までになるが総和の条件を考えるとまだ pop が必要になります．したがって，次に pop される対象である $(A_j, -j)$ が pop されます．

以上より \(A_j\) は \(X\) で pop されます．これより「 \(Y\) で \(A_j\) を \(+1\) 倍することを選択 \(\rightarrow\) \(X\) で採用されない」がいえました．
これらの議論より \(X\) と \(Y\) の結果が同じであることが示されました．