The player's level increases slower if we increment $$$k$$$.

Therefore, for every monster, there exists a threshold $$$t$$$. If $$$k \ge t$$$, it fights; if $$$k \lt t$$$, it flees.

After knowing $$$t$$$, it's straightforward to answer the queries.

$$$t$$$ only depends on the monster itself and previous monsters. So we can calculate $$$t$$$ one by one.

We can find $$$t$$$ using binary search. But we still need a data structure to efficiently find out how many monsters will flee giving a certain $$$k$$$.

Read hints.

We need a data structure that supports:

• Add an element
• Find the number of elements that $$$\leq x$$$

Either a balanced tree or a BIT indexed by element value will do. In both cases, each query is $$$O(\log n)$$$. We need $$$O(\log n)$$$ queries to binary search $$$t$$$ for one monster. The total complexity is $$$O(n \log^2 n)$$$.

However, by using some clever tricks, we can traverse the data structure once and perform binary search simultaneously. This trick eliminates a $$$\log$$$, making the whole algorithm $$$O(n \log n)$$$.

Details can be found in my code.