A single-elimination tournament is held among n players, where n is a power of two. Players are labeled 0 through n - 1, and player i has a distinct rating rating[i]; no two players share a rating. In the first round, players 0 and 1 play, players 2 and 3 play, and so on. The player with the larger rating wins and moves on; the other is eliminated. The winners keep their original left-to-right order, and the next round pairs neighboring survivors in the same way. This repeats until one champion remains.
For each player, count the total number of matches they participate in. A player receives one match for every round in which they are still in the tournament, including the round where they lose. Return an array games of length n such that games[i] is the number of matches played by player i.
When , the only player plays no match, so the answer is [0].
Example 1:
Input: rating = [2,4,1,3]
Output: [1,2,1,2]
Explanation: Everyone plays in round 1; players 1 and 3 then play in round 2, giving counts [1,2,1,2].
Example 2:
Input: rating = [4,7,2,8,1,5,3,6]
Output: [1,2,1,3,1,2,1,3]
Explanation: Player 3 wins the tournament and plays three matches; player 7 also plays three, players 1 and 5 play two, and the remaining players play one.
Example 3:
Input: rating = [1]
Output: [0]
Explanation: A single player has no opponent, so no matches are played.
Constraints:
n is a power of two.rating is .rating is a permutation of the integers from through ; therefore all ratings are distinct.