ある固定された \(K\) に対する問題を考えます。 便宜上、列の両端に大きさ \(\infty\) のスライムを番兵として追加します。

吸収可能なスライムがあればそれを吸収して損をすることはないため、 吸収可能なスライムがある限りそれらを任意の順番で貪欲に吸収していくことを繰り返すことで、\(K\) に対する問題の答えが得られます。

\(1\) 匹ずつ吸収する過程を愚直にシミュレーションすると最悪で \(\Theta(N)\) 時間かかるところを、複数のスライムの吸収をまとめて処理することで高速化します。

具体的には、吸収可能なスライムがある限り下記の手順を繰り返します。

• 高橋君の位置を \(p\)、高橋君より左にいる高橋君以上の大きさをもつスライムのうち最も右のもの位置を \(l\) 、高橋君より右にいる高橋君以上の大きさをもつスライムのうち最も左のもの位置を \(r\) とおく。
• 位置 \(l+1, \ldots, p-1, p+1, \ldots, r-1\) 番目のスライムをすべて吸収する。

\(l, r\) の定義から、\(l+1, \ldots, p-1, p+1, \ldots, r-1\) 番目のスライムは高橋君より大きさが真に小さいため、たしかに、スライムを \(1\) 匹ずつ吸収していくことの繰り返しによってそれら全部を吸収することができます。 また、上記の反復は \(O(\log A_{\max})\) 回しか行われません（ただし、\(A_{\max} \coloneqq \max_{1 \leq i \leq N} A_i\) ）。 なぜなら \(l, r\) の定義より、高橋君は \(t\) 回目の反復で、\(t-1\) 回目の反復開始時の高橋君の大きさ以上のスライムを \(1\) 匹以上吸収するため、\(t\) 回目の反復後の高橋君の大きさは \(t-1\) 回目の反復開始時の \(2\) 倍以上になるためです。

\(l, r\) を求めるのは、セグメント木上の二分探索（AtCoder Library にも実装されています）や、Sparse Table を用いた二分探索によって、\(1\) 回あたり \(O(\log N)\) 時間でできるので、 ある固定された \(K\) に対して \(O(\log N \log A_{\max})\) 時間で、すべての \(K\) を合わせて \(O(N \log N \log A_{\max})\) 時間で解くことができます。

また、与えられた数列 \(A\) の Cartesian Tree を考えることで、\(O(N\log N)\) 時間や \(O(N)\) 時間で解くこともできます。