The city of Hackerland organized a chess tournament for its citizens.
There are n participants numbered 1 to n where ith participant has potential denoted by potential[i]. The potential of each player is distinct. Initially, all players stand in a queue in order from the 1st to the nth player. In each game, the first 2 participants of the queue compete and the participant with a higher potential wins the game. After each game, the winner remains at the beginning of the queue and plays with the next person from the queue and the losing player goes to the end of the queue. The game continues until a player wins k consecutive games.
Given the potential of the participants and the deciding factor k, find the potential of the winning player.
Function Description
Complete the function getPotentialOfWinner in the editor.
getPotentialOfWinner has the following parameters:
int potential[n]: the potentials of participantslong int k: the number of consecutive matches the winning participant must win
Returns
int: the potential of the winning player
Example 1:
Input: potential = [3, 2, 1, 4], k = 2
Output: 3
Explanation:- Initial position of participants: [1, 2, 3, 4].
- Participants 1 and 2 compete. Their potentials are 3 and 2. Player 1 wins due to the higher potential. Player 1 stays at the front of the queue and player 2 moves to the back. Now their positions are [1, 3, 4, 2].
- Participants 1 and 3 compete. Their potentials are 3 and 1. 1 wins a second consecutive game. Since k = 2, player 1 has won enough consecutive games.
Return player 1's potential, 3.
Example 2:
Input: potential = [1, 3, 2, 4, 5], k = 2
Output: 3
Explanation:- Initial position of participants: [1, 2, 3, 4, 5].
- potential[1] = 3, potential[2] = 2 player 2 wins. The positions of participants after match 1: [2, 3, 4, 5, 1].
- potential[2] = 3, potential[3] = 1, player 2 wins. Since k = 2, player 2 is the winner.
Example 3:
Input: potential = [3, 2, 1, 4], k = 3
Output: 4
Explanation:Positions Potentials Consecutive
1st in line 2nd in line Winner wins
------------ ------------- ------------- -------------
[1, 2, 3, 4] 3 2 1
[1, 3, 4, 2] 3 1 2
[1, 4, 2, 3] 3 4 1
[4, 1, 2, 3] 4 3 2
[4, 2, 3, 1] 4 2 3 player 4 is the winner.
2 ≤ n ≤ 10^51 ≤ potential[i] ≤ n2 ≤ k ≤ 10^14
input:
output: