How to solve Problem MANIAC5(Warriors)?

MANIAC5
Can someone explain how to solve this problem?

1 Like

Assume warriors at positions i_1, i_2, \dots, i_k are removed in the first step. In the next step, the only warriors for whom the warrior to their immediate left changes are those at i_1 + 1, i_2 + 1, \dots, i_k + 1. These are the only warriors in danger of being removed in the second step, and some of them will be. To put it another way, every warrior that is removed in step x lies to the immediate right of some warrior that was removed in step x - 1.

Based on this, it is possible to maintain the identities of the next and previous warrior for each warrior. Warriors can be removed, and then every warrior to the right of those removed can be checked and scheduled for removal in the next step.
My solution using this approach: 23380195

Thanks for your help.
But what will be the complexity of this solution?

It’s \mathcal{O}(n). Updated code: 23435742.