Consider the problem for a fixed \(K\). For convenience, add sentinel slimes of size \(\infty\) to both ends of the line.

If there exists an absorbable slime, it never hurts to absorb it. Thus, the answer for the fixed \(K\) can be obtained by repeatedly absorbing all absorbable slimes greedily in any order as long as there exists one.

A naive simulation absorbing one slime at a time takes \(\Theta(N)\) time in the worst case. However, we can speed this up by processing multiple absorptions at once.

Specifically, as long as absorbable slimes exist, repeat the following:

• Let \(p\) be Takahashi’s position, \(l\) be the position of the rightmost slime to the left of him that is at least as large as him, and \(r\) be the position of the leftmost slime to the right of him that is at least as large as him.
• Absorb all slimes at positions \(l+1, \ldots, p-1, p+1, \ldots, r-1\).

From the definitions of \(l\) and \(r\), the slimes at positions \(l+1, \ldots, p-1, p+1, \ldots, r-1\) are strictly smaller than Takahashi, so it is certainly possible to absorb all of them by absorbing one at a time. Additionally, the above iteration is only performed at most \(O(\log A_{\max})\) times, where \(A_{\max} \coloneqq \max_{1 \leq i \leq N} A_i\). This is because, from the definitions of \(l\) and \(r\), in the \(t\)-th iteration, Takahashi absorbs at least one slime whose size is at least the size of Takahashi at the beginning of the \((t-1)\)-th iteration, so the size of Takahashi after the \(t\)-th iteration is at least double his size at the beginning of the \((t-1)\)-th iteration.

To find \(l\) and \(r\), we can use binary search on segment trees (available in AtCoder Library) or binary search using sparse tables to do it in \(O(\log N)\) time per time. Thus, the problem can be solved in \(O(\log N \log A_{\max})\) time for a fixed \(K\) and a total of \(O(N \log N \log A_{\max})\) time for all \(K\).

Alternatively, one can consider a Cartesian Tree of the given sequence \(A\) to solve this in \(O(N)\) or \(O(N \log N)\) time.