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)$