Under this constraint, the process can be simulated using a stack:

For each possible value of ~d~ from ~1~ to ~K~, iterate through all numbers in the array and push them into a stack. When the current number is ~d~, skip the pushing and remove the last ~x_d~ elements from the stack. The answer is the sum of elements that are remaining in the stack.

~\mathcal{O}(NK)~

This subtask is meant to reward suboptimal implementations of the full solution.

For each ~d~ from ~1~ to ~K~, we can solve the problem in reverse to calculate the sum of elements that will be removed from the array. In particular, for each value of ~d~ from ~1~ to ~K~, we iterate through their occurrences in reverse order while keeping track of the interval of elements that are removed.

Suppose we are at some position ~i~ and the left endpoint of the interval is ~l~. There are two cases:

• Case 1: ~i < l~
  In this case, the elements in the interval ~[i+1, l-1]~ are intact, so we add the sum of those elements to the answer. We set our new value of ~l~ to be ~i-x_d~.
• Case 2: ~i \ge l~
  In this case, we have to remove some additional elements before index ~i~. To account for this, we set our new value of ~l~ to be ~l-x_d-1~. This has the effect of "merging" two intervals of removed elements.

Using a prefix sum array, we can calculate the sum of elements in an interval in ~\mathcal{O}(1)~ time and since each position is visited at most once, this gives us our desired time complexity.

~\mathcal{O}(N + K)~