Overview

When players leave the line in increasing order of their stamina values, the problem asks us to efficiently determine “what position from the left” each player is at just before they leave.

Analysis

Players are initially lined up at positions \(1, 2, \dots, N\), but when someone leaves, the remaining players are shifted to fill the gap. Therefore, simply outputting the “original position” would be incorrect.

The key observation is as follows:

• The rank (position from the left) of a player (with original position \(i\)) just before they retire equals the number of players still remaining whose original position is \(\le i\).
  • This is because even after shifting, the “relative order” is preserved, so the only players to the left are those “still remaining with a smaller original position.”

A naive simulation would: - Delete from the array and shift elements each time someone retires (list deletion) → \(O(N)\) per operation, \(O(N^2)\) total, which would TLE for \(N \le 2 \times 10^5\).

Instead, we reformulate the problem: - Maintain whether each player “is still remaining” as \(1/0\), - Efficiently compute the prefix sum up to position \(i\) (i.e., the number of remaining players up to position \(i\)).

Algorithm

We solve with the following steps:

1. Record where the player with stamina value \(k\) is in the original line in an array pos

   • pos[k] = initial position i of that player
   • Since the input is a permutation, this is uniquely determined.

2. Consider an array \(A\) of length \(N\). Initially, all players are present, so

   • \(A[i] = 1\) (the player at position \(i\) is still remaining)
   • We manage this with a Fenwick Tree (BIT).

3. Process in order of stamina value \(k = 1..N\):

   • Let the initial position of that player be \(i = \text{pos}[k]\)
   • Compute \(\sum_{j=1}^{i} A[j]\) using the BIT This is the “position from the left just before retiring”
   • Since that player retires, set \(A[i] \leftarrow 0\), i.e., perform add(i, -1) on the BIT

Concrete Example

For example, suppose \(N=5\) and the retirement order (by stamina value) corresponds to positions \(3 \to 1 \to 5 \to 2 \to 4\).

• Initially \(A = [1, 1, 1, 1, 1]\)
• Just before position 3 leaves: \(\sum_{1..3} = 3\) → output 3, after leaving \(A = [1, 1, 0, 1, 1]\)
• Next, position 1: \(\sum_{1..1} = 1\) → output 1, after leaving \(A = [0, 1, 0, 1, 1]\)
• …and so on. We simply output the “number of remaining players in the prefix,” without ever explicitly performing the shift operation.

Complexity

• Time complexity: \(O(N \log N)\) (One BIT sum and one add operation per each \(k\))
• Space complexity: \(O(N)\) (pos and the BIT array)

Implementation Notes

• It is standard practice to implement BIT as 1-indexed, so we unify positions as \(1..N\).

• Since the input can be large, reading all at once with sys.stdin.buffer.read() is faster.

• Collecting all output and printing with join at the end is also faster.

  Source Code

import sys

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    L = data[1:]
    pos = [0] * (n + 1)
    for i, v in enumerate(L, start=1):
        pos[v] = i

    bit = BIT(n)
    for i in range(1, n + 1):
        bit.add(i, 1)

    out = []
    for k in range(1, n + 1):
        i = pos[k]
        out.append(str(bit.sum(i)))
        bit.add(i, -1)

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.