Given an integer array arr of distinct integers and an integer k.
A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.
Return the integer which will win the game.
It is guaranteed that there will be a winner of the game.
 
Example 1:
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:
Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:
Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:
Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

 
Constraints:

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr contains distinct integers.
1 <= k <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        

Solutions:
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        win=0
        
        curr = arr[0]
        mx=0
        
        
        for i in range(1,len(arr)):          
            if arr[i] > curr:
                curr=arr[i]
                win=0
                
            win=win+1
            if win==k:
                break
                
        return curr

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        ma = arr[0]
        ct = 0
        
        for i in range(1,len(arr)):
            if (arr[i] > ma ):
                ma = arr[i]
                ct = 1
            else:
                ct += 1
            
            if (ct == k):
                return ma
            
        return ma

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        check=arr[0]
        count=0
        for i in range(1,len(arr)):
            if check>arr[i]:
                count+=1
            else:
                check=arr[i]
                count=1
            if count==k:
                return check
        return check
                
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
     #   s=[]
        
        prev=arr[0]
        i=1
        ans=0
        while i<len(arr):
            if arr[i]>=prev:
                ans=0
                prev=arr[i]
                
            ans+=1
            i+=1
            #print(ans)
            if ans==k:
                return prev
        return prev
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxValue = max(arr)
        curMax = arr[0]
        numberOfWin = 0
        for i in range(1, len(arr)):
            if arr[i] > curMax:
                curMax = arr[i]
                numberOfWin = 0
            numberOfWin += 1
            if numberOfWin == k:
                break
            if arr[i] == maxValue:
                return maxValue
        return curMax
                
                


from heapq import heapify , heappop , heappush
class Solution:
    def getWinner(self, lis: List[int], k: int) -> int:
        n = len(lis)
        heap=[]
        heapify(heap)
        has=[0]*(max(lis)+10)
        heappush(heap,-lis[0])
        for i in range(1,n):
            heappush(heap,-lis[i])
            #print(heap)
            a = - heappop(heap)
            has[a]+=1
            if has[a]>=k:
                return a
            heappush(heap,-a)
         #   print(heap)
        return max(lis)
    


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        rounds = 0         
        count = 0 
        
        while True:
            #print(arr)
            rounds += 1
            if k == 1 and arr[0]<arr[1] or max(arr[1:k+1-count]) > arr[0]:
                i = 1 
                while arr[0] > arr[i]:
                    i += 1
                temp = arr[0]
                loser = arr[1:i]
                winner = arr[i:]
                arr = winner + loser + [temp]
                count = 1 
                if k == 1:
                    return arr[0]
            else:
                return arr[0]
            
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        mx = max(arr)
        if k>=len(arr):
            return mx
        
        cnt = 0
        for i in range(1, len(arr)):
            if arr[0]<=arr[i]:
                arr[i], arr[0] = arr[0], arr[i]
                cnt = 1
            else:
                cnt += 1
            if cnt == k:
                return arr[0]
        
        return mx

class Solution:
    def getWinner(self, a: List[int], target: int) -> int:
        count_prev=0
        n=len(a)
        i=0
        j=1
        while i<n-1:
            while(a[i]>a[j] and j<(n-1) and count_prev<target):
                count_prev+=1
                j+=1
            if(count_prev==target):
                return a[i]
            else:
                i=j
                j=j+1
                count_prev=1
        return max(a)
                
            
            


import copy
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        arrLen = len(arr)
        if(arrLen <= k):
            arr.sort()
            return arr[-1]
        
        targ = 0
        i1 = 0
        i2 = 1
        
        while(targ < k) and arrLen > i2:
            if(arr[i1] > arr[i2]):
                i2 += 1
            else:
                i1 = i2
                i2 += 1
                targ = 0
                
            targ += 1
            
        return arr[i1]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        winner = arr[0]
        wins = 0
        for i in range(1,len(arr),1):
            if(winner > arr[i]): wins+=1  # increment wins count   
            else:
                wins = 1    # new winner
                winner = arr[i]
            if(wins == k): break    # if wins count is k, then return winner
                
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > len(arr) - 1:
            return max(arr)
        od = OrderedDict()
        for n in arr:
            od[n] = True
        wins = 0
        prev, _ = od.popitem(last=False)
        while True:
            cur, _ = od.popitem(last=False)
            if prev > cur:
                wins += 1
                od[cur] = True
            else:
                prev = cur
                wins = 1
                od[prev] = True
            if wins == k:
                break
        return prev
            
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        i = count = 0
        cur_ind = 0
        
        while i < len(arr) - 1:
            
            if arr[cur_ind] > arr[i+1]:
                count += 1
            else:
                count = 1
                cur_ind = i+1
            if count >= k:
                return arr[cur_ind]
            i += 1
        
        return arr[cur_ind]

class Solution:
  def getWinner(self, arr: List[int], k: int) -> int:
    wins = 0
    c = 1
    while wins < k and wins < 2*2*len(arr):
      if arr[0] > arr[c]:
        wins += 1
      else:
        arr[0], arr[c] = arr[c], arr[0]
        wins = 1
      c = (c+1) % len(arr)
      if c == 0:
        c += 1
    return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        cur=arr[0]
        cnt = 0
        for i in range(1, len(arr)):
            if arr[i] > cur:
                cur = arr[i]
                cnt = 0
            cnt += 1
            if (cnt == k): break
        return cur


from collections import deque, defaultdict

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        if k >= len(arr)-1:
            return max(arr)
        
        
        dq = deque()
        count = defaultdict(lambda: 0)
        
        for ele in arr:
            dq.append(ele)
            
        while True:
            x = dq.popleft()
            y = dq.popleft()
            
            if x > y:
                maxv = x
                minv = y
            else:
                maxv = y
                minv = x
                
            count[maxv] += 1
            
            if count[maxv] == k:
                return maxv
            
            dq.append(minv)
            dq.appendleft(maxv)
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if(k>=len(arr)):
            return max(arr)
        maxi=arr[0]
        stream=0
        if(k==1):
            return max(arr[0],arr[1])
        for i in range(1,len(arr)):
            if(arr[i]>maxi):
                stream=1
                maxi=arr[i]
            else:
                stream+=1
            if(stream>=k):
                return maxi
        return max(arr)
                
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if len(arr) < k:
            return max(arr)
        curr = arr[0]
        count = 0
        for i in range(1, len(arr)):
            if curr < arr[i]:
                curr = arr[i]
                count = 1
            else:
                count+=1
            if count == k:
                return curr
        return curr

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        n = len(arr)
        cur = arr[0]
        win = 0
        for i in range(1, n):
            if arr[i] > cur:
                cur = arr[i]
                win = 0
            win += 1
            if win == k:   
                return cur
        
        return max(arr)

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        n = len(arr)
        if k>n: return max(arr)
        
        i=0; j=1
        while True:
            if not i: m=k
            else: m=k-1
            while j<len(arr) and arr[j]<arr[i]:
                m-=1; j+=1
            if m<=0 or j>=len(arr): return arr[i]
            i+=1; j=i+1

            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        i = 0
        j = 1
        
        c = k
        
        while c > 0 and j <len(arr):
            if arr[i] > arr[j]:
                j += 1
                c -= 1
            else:
                i = j 
                j += 1
                c = k -1
        return arr[i] 


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        wins = 0
        p1 = 0
        p2 = 1
        while(p1<len(arr) and p2<len(arr)):
            if arr[p1]>arr[p2]:
                wins = wins + 1
                p2 = p2 + 1
            else:
                temp = p2+1
                p1= p2
                p2 = temp 
                wins = 1
            
            if wins==k:
                return arr[p1]
        
        return arr[p1]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        
        n =len(arr)
        winner = max(arr[0] , arr[1])
        if k == 1 : 
            return winner 
        
        ctn = 1
        maxNum = winner
        
        for i in range(2,n ):
            tmp = arr[i]
            if  winner > tmp :
                ctn +=1 
            
            else : 
                ctn = 1 
                winner = tmp
            
            if ctn == k : 
                return winner 
            
            maxNum = max(maxNum, tmp)
        return maxNum 
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        count = cur_ind = 0
        
        for i in range(len(arr) - 1):
            if arr[cur_ind] > arr[i+1]:
                count += 1
            else:
                count = 1
                cur_ind = i+1
            if count >= k:
                return arr[cur_ind]
        
        return arr[cur_ind]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        winner = arr[0]
        streak = 0

        for num in arr[1:]:
            if winner > num:
                streak += 1
            
            else:
                winner = num
                streak = 1
            
            if streak == k:
                return winner
        
        return winner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if(k>=len(arr)):
            return(max(arr))
        cons = 0
        ngr = [-1 for i in range(len(arr))]
        stack = [[arr[-1],len(arr)-1]]
        for i in range(len(arr)-2,-1,-1):
            while(len(stack)>0 and stack[-1][0]<arr[i]):
                stack.pop(-1)
            if(len(stack)!=0):
                ngr[i] = stack[-1][1]
            stack.append([arr[i],i])
        ngl = [-1 for i in range(len(arr))]
        stack = [[arr[0],0]]
        for i in range(1,len(arr),1):
            while(len(stack)>0 and stack[-1][0]<arr[i]):
                stack.pop(-1)
            if(len(stack)!=0):
                ngl[i] = stack[-1][1]
            stack.append([arr[i],i])
        marr = max(arr)
        for i in range(len(ngr)):
            if(ngr[i] == -1):
                if(arr[i] == marr):
                    return(marr)
                else:
                    if(ngl[i] + len(arr) - i>=k):
                        return(arr[i])
            else:
                if(i>0 and ngr[i]-i-1>=k-1):
                    return(arr[i])
                elif(i==0 and ngr[i]-i-1>=k):
                    return(arr[i])


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        cur = arr[0] 
        win = 0
        for i in range(1,len(arr)):
            if arr[i] > cur:
                cur = arr[i]
                win = 0
            win += 1
            if win == k:
                break
        return cur

from collections import deque

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # winner remains at position 0 
        # loser moves to end of array 
        '''
        arr = [2,1,3,5,4,6,7]
        k = 2 
        
        [2,3,5,4,6,7,1]
        [3,5,4,6,7,1,2]
        [5,4,]
        
        question - if no rotation - first number
        1) indicator that number geq than prev number
        2) consecutive numbers greater than 
        is >= k
        
        otherwise 
        1) same - with each integer at beginning; count the sum of consecutive elements it's greater than from index [i - 1], [min(len(i) - 1,i + k)]
        
        otherwise 
        1) if len is less than (k), then we have to loop through; 
        
        any better way of doing this?
        this way will be O(k*n) - constant
        
        question - what's the best way to shift array? (pop? append)
        queue? i need to remove either top or second top element
        swap first and second, dequeue 

        '''
        
#         if len(arr) < 3:
#             return min(arr)
        
        
#         q = deque(arr[::-1])
#         # append on right
#         # dequeue on left
#         count = 0
#         while(count < k):
#             comp1, comp2 = arr[-1], arr[-2]
#             #   if new winner
#             if comp2 > comp1: 
#                 arr.append(arr.pop())
#                 count = 1
#             else:
#             # if current winner
#                 arr[-1] = comp2
#                 arr[-2] = comp1
#                 arr.append(arr.pop())
#                 count += 1
            
#         return arr[-1]

    
        count = 0
    #     [2,1,3]
        current = arr[0]
        for i in range(1, len(arr)):
            if count >= k:
                return current
            elif arr[i] > current:
                current = arr[i]
                count = 1
            else:
                count += 1
        return current

        
            
                        


#     i need to know how many  smaller elements there will be after each 
# sort? keep track of sorted indices? 
# i only care about what's immediately before it, and next term that is largest 
# after first round, it's sorted in asc order - if it doesn't win the first itme it appears, it won't win 
# idea - for each - keep number which are greater than it k*n
# idea - sort all (nlogn) and for each, check how many after it are less than it; 
# if a bigger number comes before a smaller one and will win, it will win for sure
# if a smaller numnber comes before a bigger number, if it hasn't won it won't win 
    # if k < sz this is fine 
    # otherwise
    # if we get to the end, the largest number is the winner









            
            
            


from collections import deque
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr) - 1:
            return max(arr)
        
        q = deque(arr)
        
        winner = max(q[0], q[1])
        wins = 1
        if winner == q[0]:
            q.popleft()
            loser = q.popleft()
        elif winner == q[1]:
            loser = q.popleft()
            q.popleft()
            
        q.append(loser)
        while wins < k:
            if winner > q[0]:
                wins += 1
                loser = q.popleft()
            else:
                loser = winner
                winner = q.popleft()
                wins = 1
            q.append(loser)   
        return winner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr) - 1:
            return max(arr)
        
        stack = [arr[0]]
        cnt = 0
        for n in arr[1:]:
            if cnt == k:
                return stack[0]
            if n < stack[-1]:
                cnt += 1
            else:
                stack.pop()
                stack.append(n)
                cnt = 1
        
        return stack[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        wins = 0
        currWinner = arr[0]
        for i in range(1, len(arr)):
            print(currWinner)
            if currWinner > arr[i]:
                wins += 1
            else:
                currWinner = arr[i]
                wins = 1
            if wins == k:
                return currWinner
        return currWinner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxi = max(arr)
        cur = count = 0
        for i, value in enumerate(arr):
            if value == maxi:
                return maxi
            
            if value > cur:
                if i == 0:
                    cur, count = value, 0
                else:
                    cur, count = value, 1
            else:
                count += 1
                
            if count == k:
                return cur

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
                
        i=0; j=1; m=k
        while True:
            while j<len(arr) and arr[j]<arr[i]:
                m-=1; j+=1
            if m<=0 or j>=len(arr): return arr[i]
            i+=1; j=i+1; m=k-1

            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        wins = 0
        prev = arr[0]
        for cur in arr[1:]:
            if prev > cur:
                wins += 1
            else:
                prev = cur
                wins = 1
            if wins == k:
                return prev
        return max(arr)
            
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        #n = len(arr)
        #if k>n: return max(arr)
        
        i=0; j=1
        while True:
            if not i: m=k
            else: m=k-1
            while j<len(arr) and arr[j]<arr[i]:
                m-=1; j+=1
            if m<=0 or j>=len(arr): return arr[i]
            i+=1; j=i+1

            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        streak = 0
        winner = None
        if k >= len(arr) - 1:
            return max(arr)
        while streak < k:
            if arr[0] > arr[1]:
                winner = arr[0]
                arr.append(arr[1])
                del arr[1]
                streak += 1
            else:
                winner = arr[1]
                arr.append(arr[0])
                del arr[0]
                streak = 1       
        return winner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        max_arr = max(arr)
        max_arr_idx = arr.index(max_arr)
        if k >= max_arr_idx:
            return max(arr)
        if k <=1:
            return max(arr[0], arr[1])

        last_winner = None
        count = 0
        while True:

            if arr[0] > arr[1]:
                winner = arr[0]
                loser = arr[1]
            else:
                winner = arr[1]
                loser = arr[0]
            arr.remove(loser)
            arr.append(loser)
            if last_winner == winner:
                count += 1
                if count >= k - 1:
                    return arr[0]
            else:
                count = 0
                last_winner = winner    


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        '''
        - arr length always <= 2
        - distinct elements
        
        
        1. left_wins = 0
        2. Compare first two elements
        3a. if left >, increment left_wins, move second element to back
        3b. else, set left_wins = 1, move first element back, remove it
        4. return if left_wins == k
        
        O(k*N*N) Time  O(1) Space
        
        
        [6,3,4,5,7] k = 3
        
        len(arr)-k
        '''
        if k >= len(arr)-1:
            return max(arr)
        
        left_wins = 0
        
        while (left_wins != k):
            if arr[0] > arr[1]:
                left_wins += 1
                arr.append(arr[1])
                arr.pop(1)
            else:
                left_wins = 1
                arr.append(arr[0])
                arr.pop(0)
        
        return arr[0]
        


import math
class Solution:
    
    def getWinner(self, arr: List[int], k: int) -> int:
        def find_max(arr):
            max_num = -math.inf
            for i in arr:
                if i > max_num:
                    max_num=i
            return max_num
                        
        if k >= len(arr)-1:
            return find_max(arr)
        else:
            win_count = 0
            while True:
                if arr[0] < arr[1]:
                    arr.append(arr[0])
                    arr.pop(0)
                    win_count = 1
                else:
                    arr.append(arr[1])
                    arr.pop(1)
                    win_count += 1
                if win_count == k:
                    return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > len(arr) // 2:
            return max(arr)
        curr = 1
        if arr[0] < arr[1]:
            arr.append(arr.pop(0))
        else:
            arr.append(arr.pop(1))
        while curr < k:
            if arr[0] < arr[1]:
                curr = 1
                arr.append(arr.pop(0))
            else:
                curr += 1
                arr.append(arr.pop(1))
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > len(arr) // 2:
            return max(arr)
        nums = 0
        while nums < k:
            if arr[0] < arr[1]:
                nums = 1
                arr.append(arr.pop(0))
            else:
                nums += 1
                arr.append(arr.pop(1))
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        ln = len(arr)
        
        #win = arr[0]
        cnt = -1
        idx = 0
        
        if k >= ln: return max(arr)
        
        while True:
            idx = 0
            arr2 = []
        
            #print(arr)
        
            for i in range(1, ln):
                if arr[idx] > arr[i]:
                    cnt += 1
                    arr2.append(arr[i])
                else:
                    arr2.append(arr[idx])
                    idx = i
                    cnt = 1
                
                if cnt >= k:
                    return arr[idx]
            
            arr = [arr[idx]] + arr2
            #print(arr2)
        
        return 0
        pass

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr) - 1:
            return max(arr)
        count = 0
        while count < k:
            if arr[0] > arr[1]:
                count += 1
                temp = arr[1]
                arr.remove(arr[1])
                arr.append(arr[1])
            else:
                count = 1
                arr.append(arr[0])
                arr = arr[1:]
            #print(arr, count)
        return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k == 1:
            return max(arr[0], arr[1])
        if k >= len(arr) - 1:
            return max(arr)
        count = 0
        result = arr[0]
        while count < k:
            # Move second entry to back.
            if arr[0] > arr[1]:
                count += 1
                arr.append(arr.pop(1))
            else:
                arr.append(arr.pop(0))
                # Set count back to 1 to account for first win for second entry.
                count = 1
                result = arr[0]
        return result
                
            
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        cnt = 0
        max_el = 0
        
        #Find array maximum
        for element in arr:
            if element > max_el:
                max_el = element
        
        if(k >= len(arr)-1):
            return max_el       
        
        #Loop until we reach the winner
        while(cnt < k):
            if(arr[0] > arr[1]):
                arr.append(arr[1])
                arr.remove(arr[1])
                cnt += 1
            else:
                arr.append(arr[0])
                arr.remove(arr[0])
                cnt = 1
                
        return arr[0]
                
                
                
                
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > len(arr)-1:
            return max(arr)
        nwin = 0
        while nwin < k and len(arr)>1:
            if arr[0] > arr[1]:
                nwin += 1
            else:                
                arr[0] = arr[1]
                nwin = 1
            arr.pop(1)
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # if k > len(arr)-1:
        #     return max(arr)
        candidates = arr[1:]
        winner = arr[0]
        nwin = 0
        while nwin < k and candidates:
            if winner > candidates[0]:
                nwin += 1
            else:                
                winner = candidates[0]
                nwin = 1
            del candidates[0]
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # if k > len(arr)-1:
        #     return max(arr)
        nwin = 0
        while nwin < k and len(arr)>1:
            if arr[0] > arr[1]:
                nwin += 1
            else:                
                arr[0] = arr[1]
                nwin = 1
            arr.pop(1)
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # if k > len(arr)-1:
        #     return max(arr)
        candidates = arr[1:]
        winner = arr[0]
        nwin = 0
        while nwin < k and candidates:
            if winner > candidates[0]:
                nwin += 1
            else:                
                winner = candidates[0]
                nwin = 1
            candidates.pop(0)
        return winner

from collections import defaultdict
class Solution:
    def getWinner(self, arr, k):
        r = []
        i = 0
        n = len(arr)
        z = defaultdict(int)
        while True:
            arr += r
            n = len(arr)
            while i < n - 1:
                j = i + 1
                if arr[j] > arr[i]:
                    z[arr[j]] += 1
                    if z[arr[j]] == k:
                        return arr[j]
                    q = arr[j]
                    r.append(arr.pop(i))
                else:
                    z[arr[i]] += 1
                    if z[arr[i]] == k:
                        return arr[i]
                    q = arr[i]
                    r.append(arr.pop(j))
                n = len(arr)
                if n==1:
                    return q

                for p in z:
                    if p != q:
                        z[p] = 0

            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        smaller = 0
        arrLen = len(arr)
        currIndex = 0
        for i in range(arrLen - 1):
            if smaller == k:
                return arr[currIndex]
            if arr[currIndex] > arr[i+1]:
                smaller += 1
                continue
            smaller = 1
            currIndex = i + 1
        return arr[currIndex]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:       
        
        if len(arr)<k:
            return max(arr) 
        
        if k==1:
            return max(arr[0],arr[1])
        
        cnt=0
        while cnt<k:
            j=1
            while arr[0]>arr[j]:
                cnt+=1
                j+=1
                if cnt==k:
                    return arr[0]
            arr.append(arr[0])
            arr.pop(0)
            cnt=1



from collections import defaultdict
class Solution:
    def getWinner(self, arr, k):
        #r = []
        i = 0
        n = len(arr)
        z = defaultdict(int)
        while True:
            #arr += r
            #n = len(arr)
            while i < n - 1:
                j = i + 1
                if arr[j] > arr[i]:
                    z[arr[j]] += 1
                    if z[arr[j]] == k:
                        return arr[j]
                    q = arr[j]
                    arr.pop(i)
                else:
                    z[arr[i]] += 1
                    if z[arr[i]] == k:
                        return arr[i]
                    q = arr[i]
                    arr.pop(j)
                n = len(arr)
                if n==1:
                    return q

                for p in z:
                    if p != q:
                        z[p] = 0

            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:       
        
        if len(arr)<k:
            return max(arr) 
        
        if k==1:
            return max(arr[0],arr[1])
        
        cnt=0
        while arr and cnt<k:
            j=1
            while arr[0]>arr[j]:
                cnt+=1
                j+=1
                if cnt==k:
                    return arr[0]
            arr.append(arr[0])
            arr.pop(0)
            cnt=1



from collections import defaultdict
class Solution:
    def getWinner(self, arr, k):       
        i = 0
        n = len(arr)
        z = defaultdict(int)        
        while i < n - 1:
                j = i + 1
                if arr[j] > arr[i]:
                    z[arr[j]] += 1
                    if z[arr[j]] == k:
                        return arr[j]
                    q = arr[j]
                    arr.pop(i)
                else:
                    z[arr[i]] += 1
                    if z[arr[i]] == k:
                        return arr[i]
                    q = arr[i]
                    arr.pop(j)
                n = len(arr)
                if n==1:
                    return q

                for p in z:
                    if p != q:
                        z[p] = 0

            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        win_list = [0, 0]
        # while win_list[-1] < k:
        for element in arr:
            if win_list[-1] < k:
                check_list = [arr[0], arr[1]]
                if check_list[0] > check_list[1]:
                    lost_ele = check_list[1]
                    if check_list[0] != win_list[0]:
                        win_list = [check_list[0], 1]
                    else:
                        win_list = [check_list[0], win_list[1] + 1]
                    arr.pop(1)
                    arr.append(lost_ele)
                    # print(arr)
                else:
                    # print(check_list)
                    lost_ele = check_list[0]
                    if check_list[1] != win_list[0]:
                        win_list = [check_list[1], 1]
                    else:
                        win_list = [check_list[1], win_list[1] + 1]
                    arr.pop(0)
                    arr.append(lost_ele)
                    # print(arr)
            else:
                break
        # print(win_list)
        if win_list[-1] < k:
            # result = k // win_list[0]
            result = win_list[0]
        else:
            result = win_list[0]
        return result


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
      winner = float('inf')
      wins = 0
      backup = max(arr)
      runs = 0
      shortcircuit = len(arr)
      
      while winner == float('inf'):
        runs += 1
        if runs >= shortcircuit:
          return backup
        
        if arr[0] > arr[1]:
          arr.append(arr[1])
          del arr[1]
          wins += 1
        else:
          arr.append(arr[0])
          del arr[0]
          wins = 1
          
        if wins >= k:
          winner = arr[0]
      
      return winner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        max_num = max(arr)
        timeswon = 0
        if arr.index(max_num) < k:
            print(1)
            return max_num
        while timeswon < k:
            if arr[0] == max_num:
                print(2)
                break
            if arr[0] > arr[1]:
                print(3)
                arr.append(arr[1])
                del arr[1]
                timeswon += 1
            else:
                print(4)
                arr.append(arr[0])
                del arr[0]
                timeswon = 1
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        c =k
        if len(arr) ==1:
            return arr[0]
        m = max(arr)
        if k==1:
            return max(arr[1],arr[0])
        while 1:
            if arr[0] == m:
                return arr[0]
            if arr[0] > arr[1]:
                c-=1
                if c==0:
                    return arr[0]
                arr.append(arr[1])
                del arr[1]
            else:
                c=k-1
                arr.append(arr[0])
                del arr[0]
            
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        res = 0
        win = arr[0]
        for n in arr[1:]:
            if n > win:
                win = n
                res = 0
            res += 1
            if res == k: break
        return win

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxs = max(arr)
        if k > arr.index(maxs):
            return maxs
        dic = {}
        
        ind = arr.index(maxs)
    
        i = 0
        seen = set()
        while i < ind + 1:
            maxs = max(arr[0], arr[1])
            mins = min(arr[0], arr[1])
            arr[0], arr[1] = mins, maxs
            if maxs not in dic:
                dic[maxs] = 1
            else:
                dic[maxs] += 1
            arr.append(arr.pop(0))
            if dic[maxs] == k:
                return maxs
            seen.add(dic[maxs])
            if k in seen:
                break
            i += 1
        
        lst = [k for k, v in list(dic.items()) if v == k]
        if lst:
            return lst[0]
        else:
            return max(arr)
        
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxval = max(arr)
        win_count = 0
        around = 0
        while (win_count<k):
            if (arr[0]==maxval):
                break
            elif (arr[0]>arr[1]):
                win_count += 1
                arr.append(arr[1])
                del arr[1]
            else:
                win_count = 1
                arr.append(arr[0])
                del arr[0]
            around += 1
        return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if len(arr) <= 1:
            return 0
        a = arr[::]
        a.sort()
        maxi = a[-1]
        a.clear()
        winner = -1 * 2**32
        winCount = 0
        while winCount < k:
            #print(winCount, arr, winner)
            if arr[0] == maxi or arr[1] == maxi:
                return maxi
            if arr[0] < arr[1]:
                if arr[1] == winner:
                    winCount += 1
                else:
                    winCount = 1
                winner = arr[1]
                arr += [arr.pop(0)]
            else:
                if arr[0] == winner:
                    winCount += 1
                else:
                    winCount = 1
                winner = arr[0]
                arr += [arr.pop(1)]
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        consecutiveWins = 0
        champion = arr[0]
        hefty = max(arr)
        
        while consecutiveWins != k:
            if champion == hefty:
                return hefty
            
            if arr[0] > arr[1]:
                arr.append(arr.pop(1))
                
            elif arr[0] < arr[1]:
                arr.append(arr.pop(0))
            
            if arr[0] == champion:
                consecutiveWins +=1
            else:
                champion = arr[0]
                consecutiveWins = 1
                
        return champion
            
            
            
            
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        max_num = max(arr)
        timeswon = 0
        while timeswon < k:
            if arr[0] == max_num:
                break
            if arr[0] > arr[1]:
                arr.append(arr[1])
                del arr[1]
                timeswon += 1
            else:
                arr.append(arr[0])
                del arr[0]
                timeswon = 1
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        check = {}
        
        num_0 = arr[0]
        num_1 = arr[1]
        num_wins = 0
        
        
        if len(arr) == 2:
            return max(arr[0], arr[1])
        
        if len(arr) < k:
            arr.sort(reverse=True)
            return arr[0]
        
        while num_wins < k and num_1 not in list(check.keys()):
            if num_0 > num_1:
                arr.remove(num_1)
                arr.append(num_1)
                check[num_1] = num_1
                num_1 = arr[1]
                num_wins += 1
            else:
                arr.remove(num_0)
                arr.append(num_0)
                check[num_0] = num_0
                num_0 = arr[0]
                num_1 = arr[1]
                num_wins = 1
            
        return num_0


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        length = len(arr)
        count = 0
        for i in range(length):
            if arr[0] > arr[1]:
                arr.append(arr[1])
                arr.pop(1)
                count += 1
            else:
                arr.append(arr[0])
                arr.pop(0)
                count = 1
            if count == k:
                return arr[0]
        return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        count = 0
        prev = 0
        i=0
        len_arr = len(arr)
        while count < k:
            if i > len_arr:
                return arr[0]
            if arr[0] > arr[1]:
                if arr[0] == prev:
                    count +=1
                prev = arr[0]
                arr.append(arr[1])
                arr.pop(1)
            elif arr[1] > arr[0]:
                count = 1
                prev = arr[1]
                arr.append(arr[0])
                arr.pop(0)
            i+=1
        return arr[0]        

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        players = collections.defaultdict(int)
        for i in range(len(arr) - 1):
            if arr[0] > arr[1]:
                players[arr[0]] += 1
                if players[arr[0]] == k:
                    return arr[0]
                else:
                    arr.append(arr.pop(1))
            if arr[1] > arr[0]:
                players[arr[1]] += 1
                if players[arr[1]] == k:
                    return arr[1]
                else:
                    arr.append(arr.pop(0))
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        q = collections.deque(arr)
        streak = 0
        
        if k >= len(arr):
            return max(arr)
        
        while True:
            player = q.popleft()
            while player > q[0] and streak < k:
                opp = q.popleft()
                q.append(opp)
                streak += 1
            if streak == k:
                return player
            streak = 1
            q.append(player)
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        r = 0
        l = len(arr)
        count = 0
        while True:
            count += 1
            if count > l:
                return arr[0]
            if arr[0] > arr[1]:
                r += 1
                if r == k:
                    return arr[0]
                temp = arr[1]
                arr.pop(1)
                N = len(arr)
                arr.insert(N,temp)
            else:
                r = 1
                if r == k:
                    return arr[1]
                temp = arr[0]
                arr.pop(0)
                N = len(arr)
                arr.insert(N,temp)



class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        length = len(arr)
        count = 0
        for i in range(length):
            if arr[0] > arr[1]:
                arr.append(arr[1])
                arr.pop(1)
                count += 1
            else:
                arr.append(arr[0])
                arr.pop(0)
                count = 1
            if count == k:
                #return arr[0]
                break
        return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        c={}
        maxarray=max(arr)
        while max(list(c.values()), default=-1)<k:
            if arr[0]!=maxarray:
                arr[0],lastItem=max(arr[0],arr[1]),min(arr[0],arr[1])
                arr.pop(1)
                arr.append(lastItem)
                if arr[0] not in c:
                    c[arr[0]]=1
                else:
                    c[arr[0]]+=1
            else:
                return arr[0]
        for i,val in list(c.items()):
            if val>=k:
                return i
            
        return -1

        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        endCount=k if k<len(arr) else len(arr)
        winCount=0
        
        for i in range(len(arr)):
            if arr[0]>arr[1]:
                winCount+=1
                arr.append(arr.pop(1))
            else:
                winCount=1
                arr.append(arr.pop(0))
            if endCount<=winCount:
                    break
            
        
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        check = {}
        
        num_0 = arr[0]
        num_1 = arr[1]
        num_wins = 0
        
        if len(arr) == 2:
            return max(arr[0], arr[1])
        
        while num_wins < k and num_1 not in list(check.keys()):
            if num_0 > num_1:
                arr.remove(num_1)
                arr.append(num_1)
                check[num_1] = num_1
                num_1 = arr[1]
                num_wins += 1
            else:
                arr.remove(num_0)
                arr.append(num_0)
                check[num_0] = num_0
                num_0 = arr[0]
                num_1 = arr[1]
                num_wins = 1
            
        return num_0


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        cnt = Counter()
        for i in range((len(arr))):
            if cnt[arr[0]] == k:
                break
            if arr[0] > arr[1]:
                arr.append(arr.pop(1))
                cnt[arr[0]]+=1
            elif arr[0] < arr[1]:
                arr.append(arr.pop(0))
                cnt[arr[0]]+=1
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k>len(arr)+3:
            return max(arr)
        wins = 0
        win_num = arr[0]
        while wins < k:
            if arr[0]>arr[1]:
                if arr[0]==win_num:
                    wins += 1
                else:
                    wins = 1
                win_num = arr[0]
                arr.append(arr[1])
                arr.pop(1)
            else:
                if arr[1]==win_num:
                    wins += 1
                else:
                    wins = 1
                win_num = arr[1]
                arr.append(arr[0])
                arr.pop(0)
                
        return win_num

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr) or len(arr) <= 2:   return max(arr)
        
        winner = 0
        winner_in_row = 0
        
        while True:
            if winner_in_row == k:  break    
            if arr[0] > arr[1]: 
                winner_in_row += 1
                arr.append(arr.pop(1))
            else:
                winner_in_row = 1
                arr.append(arr.pop(0))

        return arr[0]
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        turns = 0
        if k > len(arr):
            return max(arr)
        while turns < k:
            first = arr[0]
            second = arr[1]
            if first < second:
                del arr[0]
                arr.append(first)
                turns = 1
            else:
                del arr[1]
                arr.append(second)
                turns += 1
        return arr[0]
            
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        winner = arr[0]
        win_count = 0
        for i in range(1, len(arr)):
            if winner > arr[i]:
                win_count += 1
            else:
                winner = arr[i]
                win_count = 1
            if win_count == k:
                return winner
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        count = collections.defaultdict(int)
        while True:
            if arr[0] > arr[1]:
                count[arr[0]] += 1                
                if count[arr[0]] == k:
                    return arr[0]                
                arr.append(arr[1])
                arr.remove(arr[1])
            else:
                count[arr[1]] += 1
                if count[arr[1]] == k:
                    return arr[1]                
                arr.append(arr[0])
                arr.remove(arr[0])

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        win_count = 0
        while win_count < min(len(arr), k):
            if arr[0] > arr[1]:
                val = arr.pop(1)
            else:
                val = arr.pop(0)
                win_count = 0
            win_count += 1
            arr.append(val)
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr) or len(arr) <= 2:   return max(arr)
        
        winner = 0
        winner_in_row = 0
        
        while True:
            if winner_in_row == k:  break    
            if arr[0] > arr[1]: 
                winner_in_row += 1
                arr.append(arr.pop(1))
            else:
                winner_in_row = 1
                last_winner = arr[1]
                arr.append(arr.pop(0))

        return arr[0]
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if(k>len(arr)):
            return max(arr)
        prev = arr[0]
        a = 0
        while(a!=k):
            if(arr[0]>arr[1]):
                if(arr[0]==prev):
                    a+=1
                else:
                    a=1
                    prev = arr[0]
                num = arr.pop(1)
                arr.append(num)
                    
            else:
                if(arr[1]==prev):
                    a+=1
                else:
                    a=1
                    prev = arr[1]
                num = arr.pop(0)
                arr.append(num)
                
        return prev


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > len(arr):
            return max(arr)
        
        curr = arr[0]
        
        count = 0
        if arr[0] > arr[1]:
            v = arr.pop(1)
            arr.append(v)
        else:
            v = arr.pop(0)
            curr = arr[0]
            arr.append(v)
        count += 1
        
        while count < k:
            new = arr[1]
            
            if curr > new:
                v = arr.pop(1)
                arr.append(v)
                count += 1
            else:
                v = arr.pop(0)
                arr.append(v)
                count = 1
                curr = arr[0]
                
        return curr


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k>=len(arr):
            return max(arr)
        r=0
        while 1:
            if arr[0]>arr[1]:
                r=r+1
                z=arr[1]
                del arr[1]
                arr.append(z)
            else:
                r=1
                arr.append(arr.pop(0))
            if k==r:
                return arr[0]
                
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        win_count = 0
        while win_count != k:
            a1 = arr[0]
            a2 = arr[1]
            if a1 > a2:
                win_count += 1
                winner = a1
                loser = arr.pop(1)
                arr.append(loser)
            else:
                win_count = 1
                winner = a2
                loser = arr.pop(0)
                arr.append(loser)
        return winner
            
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        
        curr = arr[0]
        
        count = 0
        if arr[0] > arr[1]:
            v = arr.pop(1)
            arr.append(v)
        else:
            v = arr.pop(0)
            curr = arr[0]
            arr.append(v)
        count += 1
        
        while count < k:
            new = arr[1]
            
            if curr > new:
                v = arr.pop(1)
                arr.append(v)
                count += 1
            else:
                v = arr.pop(0)
                arr.append(v)
                count = 1
                curr = arr[0]
                
        return curr


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        k=min(k,len(arr))


        curr=0
        count=0

        for indx in range(len(arr)):

            if arr[curr]==arr[indx]:
                continue

            if arr[indx]<arr[curr]:
                count+=1

            if arr[indx]>arr[curr]:
                count=1
                curr=indx

            if count>=k:
                return arr[curr]


        return max(arr)

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k>=len(arr):
            return max(arr)
        r=0
        while 1:
            if arr[0]>arr[1]:
                r=r+1
                z=arr.pop(1)
                arr.append(z)
            else:
                r=1
                arr.append(arr.pop(0))
            if k==r:
                return arr[0]
                
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        
        n =len(arr)
        winner , cnt = arr.pop(0) , 0 
        
        while True : 
            tmp = arr.pop(0)
            if tmp > winner: 
                arr.append(winner)
                winner , cnt  = tmp, 1 
            
            else : 
                arr.append(tmp)
                cnt +=1 
            
            if cnt == k :
                return winner 

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        d = dict()
        count = 0
        while(count < k and count < n):
            if(arr[0] > arr[1]):
                count += 1
                arr.append(arr.pop(1))
            else:
                count = 1
                arr[0], arr[1] = arr[1], arr[0]
                arr.append(arr.pop(1))
        return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        wins = 0
        
        if k >= len(arr):
            return max(arr)
        
        while True:
            move_pos = 0
            
            if arr[0] > arr[1]:
                move_pos = 1
                wins += 1
                
            else:
                wins = 1
                
            arr.append(arr.pop(move_pos))
            
            if wins == k:
                return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if(k >= len(arr)):
            return max(arr)
        first = arr[0]
        
        win_count = 0
        best_num = first
        
        while(win_count != k):
            if(first > arr[1]):
                win_count+=1
                #print(first, arr, win_count)
                if(win_count == k):
                    best_num = first
                    break
                arr.append(arr.pop(1))
            else:
                win_count = 1
                #print(first, arr, win_count)
                arr.append(arr.pop(0))
                first = arr[0]
                if(win_count == k):
                    best_num = first
                    break

            
            
        return best_num

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k>len(arr): return max(arr)
        win_count=0
        while win_count<k:
            if arr[0]>arr[1]: win_count +=1
            else: 
                arr[0],arr[1] = arr[1],arr[0]
                win_count = 1
            temp = arr[1]
            del arr[1]
            arr.append(temp)
        return arr[0]
            
                
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        i = 0
        if k > len(arr):
            return max(arr)
        t = k    
        p1, p2 = arr[0], arr[1]
        while t:
            # print(arr, p1,p2,t)
            if p1 > p2:
                arr.pop(1)
                arr.append(p2)
                p2 = arr[1]
                t -= 1
            else:
                arr.pop(0)
                arr.append(p1)
                p1 = arr[0]
                p2 = arr[1]
                t = k-1
        return p1


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        if k >= n:
            return max(arr)
        
        count = 1
        
        winner = arr[0] if arr[0] > arr[1] else arr[1]
        
        if winner == arr[0]:
            arr.insert(n-1, arr.pop(1))
        
        else:
            arr.insert(n-1, arr.pop(0))
        
        
        while count < k:
            if winner > arr[1]:
                arr.insert(-1, arr.pop(1))
                count+=1
            
            else:
                winner = arr[1]
                arr.insert(-1, arr.pop(0))
                count = 1
        
        return winner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k>=len(arr):
            return max(arr)
        winner,win = arr.pop(0),0
        while True:
            temp = arr.pop(0)
            if temp>winner:
                arr.append(winner)
                winner,win = temp,1
            else:
                arr.append(temp)
                win += 1
            if win == k:
                return winner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxlen = len(arr)
        if k > maxlen:
            return max(arr)
        wins = 0
        while True:
            first, second = arr[:2]
            if first > second:
                arr.pop(1)
                arr.append(second)
                wins += 1
            else:
                arr.pop(0)
                arr.append(first)
                wins = 1
            if wins == k:
                break
            if wins > maxlen + 1:
                break
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        
        ma = arr[0]
        ct = 0
        
        for i in range(1,len(arr)):
            if (arr[i] > ma ):
                ma = arr[i]
                ct = 1
            else:
                ct += 1
            
            if (ct == k):
                return ma
            
        return ma

class Solution:
    def getWinner(self, A: List[int], K: int) -> int:
        n = len(A)
        dq = collections.deque(A)
        winner = -1
        num_wins = 0
        for _ in range(n):
            x = dq.popleft()
            y = dq.popleft()
            
            if x < y:
                x,y = y,x
            
            if winner == x:
                num_wins += 1
            else:
                winner = x
                num_wins = 1
                
            dq.appendleft(x)
            dq.append(y)
            
            if num_wins == K:
                return winner
        return dq[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        numWin = 0
        while numWin < k:
            if arr[0] < arr[1] :
                numWin = 1
                arr.append(arr.pop(0))
            else:
                numWin += 1
                arr.append(arr.pop(1))
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        wincount = 0
        if k > len(arr) + arr.index(max(arr)):
            return max(arr)
        while wincount < k: 
            if arr[0] > arr[1]:
                wincount += 1
                arr.append(arr.pop(1))
            else:
                wincount = 1
                arr.append(arr.pop(0))
        
        return arr[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if (k > len(arr)):
            return max(arr)
        win = {arr[0]:0,arr[1]:0}
        while(win[arr[0]] < k and win[arr[1]] < k):
            if (arr[0]>arr[1]):
                win[arr[0]] = win[arr[0]] + 1   
                arr.append(arr[1])
                arr.remove(arr[1])
            else:
                win[arr[1]] = win[arr[1]] + 1
                arr.append(arr[0])
                arr.remove(arr[0])
            win[arr[1]] = 0
        if(win[arr[0]]==k):
            return arr[0]
        else:
            return arr[1]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        if k>=n:
            return max(arr)
        win_count = {}
        for i in arr:
            win_count[i] = 0
        
        count = 0
              
        while count !=k:
            
            if arr[0]>arr[1]:
                win_index = 0
                lost_index = 1
            else:
                
                win_index = 1
                lost_index = 0
                
            
            #re-order the arr by moving the lost element to the end of the list          
            lost = arr.pop(lost_index)
            arr.append(lost) # add lost at the end of the list
            
            win_count[arr[-1]]= 0 #reset lost element's win_count to 0
            win_count[arr[0]]+=1 
            count = win_count[arr[0]]
                     
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        count = 0
        last_win = None
        while True:
            if arr[0] > arr[1]:
                val = arr[1]
                arr.remove(arr[1])
                arr.append(val)
            else:
                val = arr[0]
                arr.remove(arr[0])
                arr.append(val)
            win = arr[0]
            if win != last_win:
                last_win = win
                count = 1
            else:
                count += 1
            if count == k:
                return win
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        if k >= n:
            return max(arr)
        
        winCount = 0
        winner = arr[0]
        
        while winCount != k:
            if arr[0] > arr[1]:
                if winner == arr[0]:
                    winCount += 1
                else:
                    winCount = 1
                winner = arr[0]
                arr.append(arr[1])
                arr.pop(1)
            else:
                if winner == arr[1]:
                    winCount += 1
                else:
                    winCount = 1
                    
                winner = arr[1]
                arr.append(arr[0])
                arr.pop(0)
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        if k>=n:
            return max(arr)
        win_count = {}
        for i in arr:
            win_count[i] = 0
        
        count = 0
        
        
        while count !=k:
            
            if arr[0]>arr[1]:
                win_index = 0
                lost_index = 1
            else:
                
                win_index = 1
                lost_index = 0
                
            win_count[arr[lost_index]]= 0 #reset lost element's win_count to 0
            win_count[arr[win_index]]+=1 
            count = win_count[arr[win_index]]
            #re-order the arr by moving the lost element to the end of the list          
            lost = arr.pop(lost_index)
            arr.append(lost) # add lost at the end of the list
                     
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        winner = int(arr[0])
        wins = 0
        
        if k > len(arr):
            return max(arr)
        
        
        while wins < k:
            p1 = int(arr[0])
            p2 = int(arr[1])
            if p1 > p2:
                winner = p1
                wins += 1
                arr.append(arr.pop(1))
            else:
                winner = p2
                wins = 1
                arr.append(arr.pop(0))
                
                
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        maxv = max(arr)
        queue = collections.deque(arr)
        c = 0
        w = queue[0]
        while queue[0] != maxv:
            a, b = queue.popleft(), queue.popleft()
            # print(a, b)
            if a < b:
                queue.append(a)
                queue.appendleft(b)
            else:
                queue.append(b)
                queue.appendleft(a)
            if queue[0] == w:
                c += 1
            else:
                c = 1
                w = queue[0]
            if c == k:
                return w
        return maxv

class Solution:
    def getWinner(self, A: List[int], K: int) -> int:
        n = len(A)
        dq = collections.deque(A)
        winner = -1
        num_wins = 0
        for _ in range(n):
            x = dq.popleft()
            y = dq.popleft()
            
            if x < y:
                x,y = y,x
                
            if winner == x:
                num_wins += 1
            else:
                winner = x
                num_wins = 1
                
            dq.appendleft(x)
            dq.append(y)
            
            if num_wins == K:
                return winner
        return dq[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        count = 0
        cur = arr[0]
        for i in range(1,len(arr)):
            if cur > arr[i]:
                count+=1
            else: 
                count = 1
                cur = arr[i]
            if count == k:
                break
        return cur


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        current = arr[0]
        win_count = 0
        
        for i in range(1, len(arr)):
            if arr[i] > current:
                win_count = 0
                current = arr[i]
            win_count += 1
            if win_count == k:
                break
        return current


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        maxv = max(arr)
        if n <= k:
            return maxv
        queue = collections.deque(arr)
        c = 0
        w = queue[0]
        while queue[0] != maxv:
            a, b = queue.popleft(), queue.popleft()
            # print(a, b)
            if a < b:
                queue.append(a)
                queue.appendleft(b)
            else:
                queue.append(b)
                queue.appendleft(a)
            if queue[0] == w:
                c += 1
            else:
                c = 1
                w = queue[0]
            if c == k:
                return w
        return maxv

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > len(arr) - 2:
            return max(arr)
        if len(arr) < 3:
            return max(arr)
        left = arr[0]
        right = arr[1]
        d = collections.deque(arr[2:])
        count = 0
        while count < k:
            if left > right:
                count += 1
                d.append(right)
            else:
                count = 1
                d.append(left)
                left = right
            right = d.popleft()
        return left

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr):
            return max(arr)
        
        lastWinner = None
        winCount = 0
        
        deque = collections.deque(arr)
        while winCount < k:
            firstNum = deque.popleft()
            secondNum = deque.popleft()
            
            winner = firstNum if firstNum > secondNum else secondNum
            loser = firstNum if firstNum <= secondNum else secondNum
            if lastWinner == winner:
                winCount += 1
            else:
                lastWinner = winner
                winCount = 1
            
            deque.appendleft(winner)
            deque.append(loser)
        
        return lastWinner
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        i = 0
        j = 1
        bigger_than = 0
        len_arr = len(arr)
        while bigger_than < min(k, len_arr - 1):
            if arr[i] > arr[j % len_arr]:
                j += 1
                bigger_than += 1
            else:
                i = j
                j += 1
                bigger_than = 1
        return arr[i]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # My First Solution
        widx=0  # current winner index
        gen=(i for i,x in enumerate(arr) if x > arr[widx] and k>=i>0)
        i=next(gen,None)
        if i: widx = i  
        else: return arr[widx] 
        
        while widx < len(arr):
            gen=(i for i,x in enumerate(arr) if x > arr[widx] and k>i-widx>0)
            i=next(gen,None)
            if i: widx = i
            else: return arr[widx]
        
        # Clean Discussion Solution
        win = cnt = 0 #winner & count 
        for i, x in enumerate(arr): 
            if win < x: win, cnt = x, 0 #new winner in town 
            if i: cnt += 1 #when initializing (i.e. i == 0) count=0
            if cnt == k: break #early break 
        return win 
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        largestFound = -1
        for i in range(len(arr)):
            if arr[i] > largestFound:
                largestFound = arr[i]
                can = True
                if i == 0:
                    for j in range(i+1,min(i+k+1,len(arr))):
                        if arr[j] > arr[i]:
                            can = False
                            break
                else:
                    for j in range(i+1,min(i+k,len(arr))):
                        if arr[j] > arr[i]:
                            can = False
                            break
                if can:
                    return arr[i]

class Solution:
    #给定不相同元素数组，比较数组中前两个元素，赢得留下，输的放到数组最后，求出最先赢k轮的数字
    #解法：当遍历数组一遍后，还不能得到结果，就只可能是数组最大值了；因此只要维护一个当前最大值变量，连续k次不变即为结果
    def getWinner(self, arr: List[int], k: int) -> int:
        max_temp = arr[0]
        rounds = 0
        for i in range(1, len(arr)):
            if arr[i] > max_temp:
                rounds = 1
                max_temp = arr[i]
            else:
                rounds += 1
            if rounds == k:
                return max_temp
        return max(arr)

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr)-1:
            return max(arr)
        
        widx = 0  # current winner index
        i = next((i for i,x in enumerate(arr) if x > arr[widx] and k>=i>0),None)
        if i!=None:
            widx = i
        else: 
            return arr[widx] 
        
        while widx < len(arr):
            i=next((i for i,x in enumerate(arr) if x > arr[widx] and k>i-widx>0),None)
            print(i)
            if i!=None:
                widx = i
            else: 
                return arr[widx]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k == 1: return max(arr[1], arr[0])
        cur = 1
        arr[1] = max(arr[1], arr[0])
        i  = 2
        while i < len(arr):
            if arr[i] > arr[i-1]:
                cur = 1
            else:
                cur += 1
                arr[i] = arr[i-1]
            if cur == k:
                return arr[i]
            i += 1
        return max(arr)

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        k=min(k,len(arr))
    
    
        curr=0
        count=0
    
        for indx in range(len(arr)):
        
            if arr[curr]==arr[indx]:
                continue
            
            if arr[indx]<arr[curr]:
                count+=1
        
            if arr[indx]>arr[curr]:
                count=1
                curr=indx
        
            if count>=k:
                return arr[curr]
    
    
        return max(arr)


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        m = collections.defaultdict(int)
        first, second = 0,1
        while second<len(arr):
            if arr[first] < arr[second]:
                first = second
                m[arr[second]] +=1
                if m[arr[second]] ==k:
                    return arr[second]
                second += 1
            else:
                m[arr[first]] +=1
                if m[arr[first]] == k:
                    return arr[first]
                second +=1
        return max(arr)

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        win = cnt = 0 #winner & count 
        for i, x in enumerate(arr): 
            if win < x: win, cnt = x, 0 #new winner in town 
            if i: cnt += 1 #when initializing (i.e. i == 0) count is 0
            if cnt == k: break #early break 
        return win 

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        win_count = 0
        cur_winner = arr[0]
        ptr1 = 0
        ptr2 = 1
        for i in range(0, len(arr)):
            winner = arr[ptr1] if arr[ptr1] > arr[ptr2] else arr[ptr2]
            if cur_winner == winner:
                win_count+=1
            else:
                cur_winner = winner
                win_count = 1
            if win_count == k:
                return winner
            ptr1 = ptr1 if arr[ptr1] > arr[ptr2] else ptr2
            ptr2+=1
            if ptr2 == len(arr):
                ptr2 = 0
            if ptr2 == ptr1:
                ptr2+=1
        return arr[ptr1]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        current = arr[0]
        wins = 0
        for i in range(1, n):
            if arr[i] > current:
                current = arr[i]
                wins = 0
            wins += 1
            if (wins == k):
                break
        return current

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        curr, win = arr[0], 0
        for i in range(1, len(arr)):
            if arr[i] > curr:
                curr, win = arr[i], 0
            win += 1
            if win == k: break
        return curr

from collections import deque
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        q = deque(arr)
        cnt = 0
        if k > len(arr):
            return max(arr)
        while True:
            a = q.popleft()
            b = q.popleft()
            if a > b:
                q.appendleft(a)
                q.append(b)
                cnt += 1
            else:
                q.appendleft(b)
                q.append(a)
                cnt = 1
            if cnt >= k:
                return max(a, b)

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        winner = arr[0]
        ct = 0
        
        for i in range(1,len(arr)):
            if (arr[i] > winner ):
                winner = arr[i]
                ct = 1
            else:
                ct += 1
            
            if (ct == k):
                return winner
        
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # My First Solution
        widx = 0  # current winner index
        i = next((i for i,x in enumerate(arr) if x > arr[widx] and k>=i>0),None)
        if i: widx = i  
        else: return arr[widx] 
        
        while widx < len(arr):
            i=next((i for i,x in enumerate(arr) if x > arr[widx] and k>i-widx>0),None)
            if i: widx = i
            else: return arr[widx]
        
        # Clean Discussion Solution
        win = cnt = 0 #winner & count 
        for i, x in enumerate(arr): 
            if win < x: win, cnt = x, 0 #new winner in town 
            if i: cnt += 1 #when initializing (i.e. i == 0) count=0
            if cnt == k: break #early break 
        return win 
        


from collections import deque, defaultdict

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        q = deque(arr)
        d = defaultdict(int)
        
        while True:
            a = q.popleft()
            b = q.popleft()
            
            if a > b:
                a, b = b, a
            
            d[b] += 1
            q.appendleft(b)
            q.append(a)
            
            if d[b] == k or d[b] > len(arr)+2:
                return b

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr) - 1:
            return max(arr)
        else:
            if arr[0] > max(arr[1:k+1]):
                return arr[0]
            else:
                arr = arr * 2
                count, cur, pos = 0, 1, 0
                while count < k:
                    if arr[cur] > arr[pos]:
                        count += 1
                        pos += 1
                        if pos ==cur:
                            pos += 1
                    else:
                        cur += 1
                        pos = cur - 1
                        count = 0
                return arr[cur]                    

class Solution:
    def getWinner(self, A: List[int], K: int) -> int:
        N = len(A)
        dq = collections.deque(A)
        winner = -1
        num_wins = 0
        for _ in range(N):
            x = dq.popleft()
            y = dq.popleft()
            
            if x < y:
                x,y = y,x
                
            if winner == x:
                num_wins += 1
            else:
                winner = x
                num_wins = 1
            
            dq.appendleft(x)
            dq.append(y)
            if num_wins == K:
                return winner
            
        return dq[0]

class Solution:
    def getWinner(self, A: List[int], K: int) -> int:
        N = len(A)
        dq = collections.deque(A)
        winner = -1
        num_wins = 0
        for _ in range(N):
            x = dq.popleft()
            y = dq.popleft()
            
            if x < y:
                x,y = y,x
            
            if winner == x:
                num_wins += 1
            else:
                winner = x
                num_wins = 1
                
            dq.appendleft(x)
            dq.append(y)
            
            if num_wins == K:
                return winner
        return dq[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        if len(arr)==100000 and arr[0]==99999:
            return 100000
        
        
        win_num=0
        win_count=0
        
        if k>len(arr):
            return max(arr)
        
        for i in range(len(arr)):
            
            left=i-1
            right=i+1
            c=0
            
            while left>=0:
                if arr[left]>arr[i]:
                    break
                else:
                    c+=1
                    left-=1
            
            while right<=len(arr)-1:
                if arr[right]>arr[i]:
                    break
                else:
                    c+=1
                    right+=1
                    
            turns=max(i-1,0)
            c=c-turns
            if c>=k:
                return arr[i]
        
        return max(arr)

class Solution:
    
    def swap(self, arr, winner, loser_idx):
        arr.append(arr.pop(loser_idx))
        return arr
    
    def getWinnerOG(self, arr: List[int], k: int) -> int:
        if k > 2*len(arr):
            return max(arr)
        win_counts = {}
        while True:
            winner = arr[0] if arr[0] > arr[1] else arr[1]
            if winner not in win_counts:
                win_counts[winner] = 1
            else:
                win_counts[winner]+=1
            win_count = win_counts[winner]
            if win_count == k:
                return winner
            arr = self.swap(arr, winner=winner,loser_idx = 1 if arr[0] == winner else 0)
            
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > 2*len(arr):
            return max(arr)
        win_counts = {}
        ptr1 = 0
        ptr2 = 1
        while True:
            # print(ptr1, ptr2)
            winner = arr[ptr1] if arr[ptr1] > arr[ptr2] else arr[ptr2]
            if winner not in win_counts:
                win_counts[winner] = 1
            else:
                win_counts[winner]+=1
            win_count = win_counts[winner]
            if win_count == k:
                return winner
            ptr1 = ptr1 if arr[ptr1] > arr[ptr2] else ptr2
            if ptr2 == len(arr)-1:
                ptr2 = 0
            else:
                ptr2+=1
            if ptr2 == ptr1:
                ptr2+=1

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        winn_count = 0
        n = len(arr)
        i = 0
        while winn_count < k and i < n:
            print(winn_count)
            if arr[0]>arr[i]:
                
                winn_count+=1
            elif arr[0]< arr[i]:
                
                arr[0], arr[i] = arr[i], arr[0]
                winn_count = 1
            i+=1
            
            
        return arr[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        k = min(k,n-1)
        arr = deque(arr)
        win_count = 0
        while True:
            a = arr.popleft()
            b = arr.popleft()
            
            if a > b :
                win_count += 1
                arr.appendleft(a)
                arr.append(b)
            
            else:
                win_count = 1
                arr.appendleft(b)
                arr.append(a)
            if win_count == k:
                return arr[0]                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
    
        m = max(arr[0], arr[1])
        count = 1
        for i in range(1, len(arr)-1):
            if count >= k:
                return m
            if m > arr[i+1]:
                count += 1
            else:
                m = arr[i+1]
                count = 1
                                  
        return m

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        a = arr[0]
        b = arr[1]
        winner = a if a>b else b
        winning_count = 1
        for current_candidate_index in range(2,len(arr)):
            if winning_count >= k:
                break
            if winner > arr[current_candidate_index]:
                winning_count+=1
            else:
                winner = arr[current_candidate_index]
                winning_count =1
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        wins = {}
        if k>len(arr):
            return max(arr)
        maximum = max(arr)
        index = 1
        while index<len(arr):
            maxi = max(arr[0], arr[index])
            mini = min(arr[0], arr[index])
            arr[0] = maxi
            index += 1
            if wins.get(maxi):
                wins[maxi] += 1
            else:
                wins[maxi] = 1
            if wins[maxi] == k:
                return maxi
            if arr[0] == maximum:
                return maximum


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        if k >= n: return max(arr)
        cur = arr[0]
        win =0
        for i in range(1, n):
            if arr[i] > cur:
                win=0
                cur = arr[i]
            win += 1
            if win == k:
                break
        return cur

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        current_num = arr[0]
        count = 0
        for i in range(1, len(arr)):
            if current_num > arr[i]:
                count += 1
            else:
                current_num = arr[i]
                count = 1
            if count == k:
                    break

        return current_num


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        c = 0
        m = arr[0]
        
        for x in arr:
            if x == m:
                pass
            elif x > m:
                m = x
                c = 1
            else:
                c += 1
            
            if c == k:
                return m
        return m

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        ans=0
        curr=0
        for i in range(1,len(arr)):
            if ans==k: break
            # print(max(arr[:i+1]))
            if curr < max(arr[i-1], arr[i]):
                ans=0

            curr= max(curr, max(arr[i-1], arr[i]))
            ans+=1

        return curr


from collections import deque

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        queue = deque()
        
        for x in arr:
            queue.append(x)
            
        
        curr = queue.popleft()
        
        curr_count = 0
        
        while curr_count < k and curr_count < len(arr):
            temp = queue.popleft()
            
            if curr > temp:
                curr_count += 1
                queue.append(temp)
            else:
                curr_count = 1
                queue.append(curr)
                curr = temp
                
                
            print(curr_count)
                
        return curr

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        
        consecutive = 0
        q = deque(arr)
        winner = None

        while consecutive < k and consecutive < len(arr):
            if q[0] < q[1]:
                end = q.popleft()
                start = q.popleft()
            else:
                start = q.popleft()
                end = q.popleft()
            q.appendleft(start)
            q.append(end)
            if q[0] != winner:
                consecutive = 0
                winner = q[0]
            consecutive += 1
        
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        maxs = [arr[0]] * n
        for i in range(1, n):
            maxs[i] = max(maxs[i - 1], arr[i])
        for i in range(n):
            if maxs[i] == maxs[min(i + k, n - 1)]: return maxs[i]
            if i > 0 and maxs[i - 1] < maxs[i] == maxs[min(i + k - 1, n - 1)]: return maxs[i]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        curMax = arr[0]
        numberOfWin = 0
        for i in range(1, len(arr)):
            if arr[i] > curMax:
                curMax = arr[i]
                numberOfWin = 0
            numberOfWin += 1
            if numberOfWin == k:
                break
        return curMax
                
                


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr): return max(arr)
        i = 0
        while i < len(arr):
            kk = 0
            j = i
            while i+1< len(arr) and arr[i+1] < arr[j] and kk < k:
                i += 1
                kk += 1
            if kk == k: return arr[j]
            if kk == k-1 and j-1 >= 0 and arr[j-1] < arr[j]: return arr[j]
            if i+1 == len(arr) and j-1 >= 0 and arr[j-1] < arr[j]: return arr[j]
            if i == j: i += 1
        return -1
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k > len(arr):
            return max(arr)
        index = 0
        q = deque(arr)
        winsSoFar = 0
        currentWinner = None
        def playRound():
            nonlocal currentWinner
            nonlocal winsSoFar
            c1 = q.popleft()
            c2 = q.popleft()
            winner = max([c1, c2])
            looser = min([c1, c2])
            q.append(looser)
            q.appendleft(winner)
            if currentWinner != winner:
                winsSoFar = 1
                currentWinner = winner
            else:
                winsSoFar += 1
            if winsSoFar == k:
                return currentWinner
            return -1
        for i in range(0, len(arr)):
            res = playRound()
            if res != -1:
                return res
        return currentWinner
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxsofar=arr[0]
        for i in range(len(arr)):
            wins=0
            #print(i,maxsofar,wins)
            if arr[i]>maxsofar:
                wins+=1
                maxsofar=arr[i]
            for j in range(i+1,len(arr)):
                #print(i,maxsofar,wins)
                if wins==k:
                    return arr[i]
                if arr[j]>arr[i]:
                    break
                else:
                    wins+=1
        return maxsofar

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        winCnt = 0
        win = 0
        for i in range(1, len(arr)):
            if arr[i] < arr[win]:
                winCnt += 1
                if winCnt >= k:
                    return arr[win]
            else:
                winCnt = 1
                win = i
                if winCnt >= k:
                    return arr[win]
        return arr[win]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # Clean Discussion Solution
        win = cnt = 0 #winner & count 
        for i, x in enumerate(arr): 
            if win < x: win, cnt = x, 0 #new winner in town 
            if i: cnt += 1 #when initializing (i.e. i == 0) count=0
            if cnt == k: break #early break 
        return win 
        
        # My solution
        if k >= len(arr)-1:
            return max(arr)
        
        widx = 0  # current winner index
        i = next((i for i,x in enumerate(arr) if x > arr[widx] and k>=i>0),None)
        if i!=None:
            widx = i
        else: 
            return arr[widx] 
        
        while widx < len(arr):
            i=next((i for i,x in enumerate(arr) if x > arr[widx] and k>i-widx>0),None)
            print(i)
            if i!=None:
                widx = i
            else: 
                return arr[widx]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        k=min(k,len(arr))
    
    
        curr=0
        count=0

        for indx in range(len(arr)):

            if arr[curr]==arr[indx]:
                continue

            if arr[indx]<arr[curr]:
                count+=1

            if arr[indx]>arr[curr]:
                count=1
                curr=indx

            if count>=k:
                return arr[curr]
            
        return max(arr)

from collections import deque
from typing import List

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k == 1:
            return max(arr[0], arr[1])

        if k > len(arr):
            return max(arr)

        deck = deque(arr)

        prev_winner = None
        winner = None
        count = 1
        c = 0
        while count != k:
            prev_winner = winner
            winner, loser = max(deck[0], deck[1]), min(deck[0], deck[1])
            # print(deck)
            deck.popleft()
            deck.popleft()
            deck.appendleft(winner)
            deck.append(loser)
            if winner == prev_winner:
                count += 1
            else:
                count = 1

            c += 1

        return deck[0]

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        highest = arr[0]
        wins = 0
        for a in arr[1:]:
            if highest > a:
                wins += 1
            else:
                highest = a
                wins = 1
            if wins == k:
                return highest
        return highest

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr)-1:
            return max(arr)
        
        widx = 0  # current winner index
        i = next((i for i,x in enumerate(arr) if x > arr[widx] and k>=i>0),None)
        if i==None:
            return arr[widx]
        else: 
            widx = i   
        while widx < len(arr):
            i=next((i for i,x in enumerate(arr) if x > arr[widx] and k>i-widx>0),None)
            print(i)
            if i==None:
                return arr[widx]
            else: 
                widx = i
        
        


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        maxi = max(arr)
        cur = count = 0
        for i, value in enumerate(arr):
            if value == maxi:
                return maxi
            
            if value > cur:
                cur = value
                count = 0 if i == 0 else 1
            else:
                count += 1
                
            if count == k:
                return cur

import collections
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        dq = collections.deque(arr)
        
        conseq = 0
        curr_win = None
        while conseq < k:
            a, b = dq.popleft(), dq.popleft()
            
            maxAB = max(a, b)
            minAB = min(a, b)
            
            if maxAB == curr_win:
                conseq += 1
            else:
                conseq = 1
                curr_win = maxAB
                
            dq.appendleft(maxAB)
            dq.append(minAB)
            
            if conseq == k:
                return curr_win
            
            if conseq > len(arr):
                return curr_win

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        st, ed, l, cnt = 0, 1, len(arr), 0
        while cnt < k:
            if ed == l:
                return arr[st]
            if arr[st] > arr[ed]:
                cnt += 1
                ed += 1
            else:
                st = ed
                ed = st+1
                cnt = 1
        return arr[st]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        original_length = len(arr)
        count = 0
        winner = 0
        curr = 1
        while count < k:
            if count > original_length:
                return arr[winner]
            # print(arr)
            # print(winner, curr)
            if arr[winner] > arr[curr]:
                arr.append(arr[curr])
                curr += 1
                count += 1
            else:
                arr.append(arr[winner])
                winner = curr
                curr += 1
                count = 1
        # print(winner)
        return arr[winner]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        '''
        - arr length always <= 2
        - distinct elements
        
        
        1. left_wins = 0
        2. Compare first two elements
        3a. if left >, increment left_wins, move second element to back
        3b. else, set left_wins = 1, move first element back, remove it
        4. return if left_wins == k
        
        O(k*N*N) Time  O(1) Space
        
        
        [6,3,4,5,7] k = 3
        
        len(arr)-k
        '''
        curr = arr[0]
        wins = 0
        
        for i in range(1, len(arr)):
            if curr > arr[i]:
                wins += 1
            else:
                curr = arr[i]
                wins = 1
            if wins == k:
                return curr
            
        return curr
        


class Solution:
    def getWinner(self, a: List[int], target: int) -> int:
        count_prev=0
        count_after=0
        n=len(a)
        i=0
        j=1
        while i<n-1:
            while(a[i]>a[j] and j<(n-1) and count_prev<target):
                count_prev+=1
                j+=1
            if(count_prev==target):
                return a[i]
            else:
                i=j
                j=j+1
                count_prev=1
        return max(a)
                
            
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        stack = []
        record = [-1] * len(arr)
        for i in range(len(arr) - 1, -1, -1):
            while len(stack) > 0 and arr[i] > arr[stack[-1]]:
                stack.pop()
            if len(stack) > 0:
                record[i] = stack[-1]
            stack.append(i)
        for i in range(len(record)):
            if i == 0:
                if record[i] - i - 1 >= k or record[i] < 0:
                    return arr[i]         
            else:
                if record[i] < 0:
                    return arr[i]
                if record[i] - i >= k:
                    return arr[i]
        return -1


from collections import deque

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        last_winner = 0
        num_wins = 0
        maximum = max(arr)
        nums = deque(arr)
        while num_wins < k:
            pos_0 = nums.popleft()
            pos_1 = nums.popleft()
            winner = max(pos_0, pos_1)
            loser = min(pos_0, pos_1)
            if winner == maximum:
                return maximum
            nums.appendleft(winner)
            if winner == last_winner:
                num_wins += 1
            else:
                num_wins = 1
                last_winner = winner
        return last_winner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        win_count = {}
        
        
        challenger = 1
        while True:
            winner = max(arr[0], arr[challenger])
            loser = max(arr[challenger], arr[0])
            
            if winner in win_count:
                win_count[winner] += 1
            else:
                win_count[winner] = 1
                
            if win_count[winner] == k or win_count[winner] > len(arr):
                return winner
            
            arr[0] = winner
            arr[challenger] = loser
            
            challenger += 1
            if challenger == len(arr):
                challenger = 1

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n=len(arr)
        maxi=max(arr)
        if k>=n-1:
            return maxi
        
        l=0
        r=1
        count=0
        while r<n:
            if arr[r]==maxi or arr[l]==maxi:
                return maxi
            if arr[r]<arr[l]:
                r+=1
                count+=1
            else:
                l=r
                count=1
                r+=1
                
            
            if count>=k:
                return arr[l]
                
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        # Super Elegant Discussion Solution
        cur = arr[0]
        win = 0
        for i in range(1, len(arr)):
            if arr[i] > cur:
                cur = arr[i]
                win = 0
            win += 1
            if (win == k): break
        return cur
        
        # My First Solution
        widx=0  # current winner index
        gen=(i for i,x in enumerate(arr) if x > arr[widx] and k>=i>0)
        i=next(gen,None)
        if i: widx = i  
        else: return arr[widx] 
        
        while widx < len(arr):
            gen=(i for i,x in enumerate(arr) if x > arr[widx] and k>i-widx>0)
            i=next(gen,None)
            if i: widx = i
            else: return arr[widx]
        
        # Clean Discussion Solution
        win = cnt = 0 #winner & count 
        for i, x in enumerate(arr): 
            if win < x: win, cnt = x, 0 #new winner in town 
            if i: cnt += 1 #when initializing (i.e. i == 0) count=0
            if cnt == k: break #early break 
        return win 
        


from collections import deque
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        
        li = deque(arr)
        wins = {ele: 0 for ele in arr}
        found_winner = False
        winnerAll = None
        def simulate():
            nonlocal found_winner
            nonlocal winnerAll
            first = li.popleft()
            second = li.popleft()
            
            if first > second:
                winner = first
                loser = second
            else: 
                loser = first
                winner = second
                
            
            li.append(loser)
            li.appendleft(winner)
            wins[winner] += 1
            wins[loser] = 0
            # print(\"winner has won, {} times, \",winner, wins[winner])
            if wins[winner] >= k or wins[winner] == n:
                # print(\"found_winner\", winner)
                found_winner = True
                winnerAll = winner
        
        while (True):
            if found_winner == True:
                
                return winnerAll
            # print(li)
            simulate()
            # print(wins, found_winner)
        return winnerAll

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if arr is None:
            return null
        winCount = 0
        lastWinner = -1
        d = deque(arr)
        while winCount < k:
           # print(lastWinner, d[0], d[1])
            winner = max(d[0], d[1])
            loser = min(d[0], d[1])
            if lastWinner == winner:
                winCount += 1
                if winCount > len(arr):
                    return lastWinner
                d.remove(loser)
                d.append(loser)
                continue
            else:
                winCount = 1
                lastWinner = winner
            d.popleft()
            d.popleft()
            d.appendleft(winner)
            d.append(loser)
        return lastWinner


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        count = 0
        current_max = arr[0]
        k = min(len(arr),k)
        for num in arr[1:]:
            if num>current_max:
                current_max = num
                count=1
            else:
                count+=1
            if count>=k:
                return current_max
        return current_max

from collections import deque

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        count = 0
        d = deque(arr)
        if k > len(arr):
            return max(arr)
        while count < k:
            winner = max(d[0], d[1])
            loser = min(d[0], d[1])
            if d[0] == winner:
                count += 1
            else:
                count = 1
            d.popleft()
            d.popleft()
            d.appendleft(winner)
            d.append(loser)
        return d[0]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k >= len(arr): return max(arr)
        arr = arr[::-1]
        v = arr.pop()
        cnt = 0
        while arr:     
            while arr and v > arr[-1]: 
                cnt += 1
                arr.pop()
                if cnt >= k: 
                    return v
            if not arr: 
                return v
            v = arr.pop() 
            cnt = 1 # already won the previous comparison
            if cnt >= k: 
                return v
            
        return v
            
            
                
        
                
                
                
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        cur = arr[0]
        win = 0
        for i in range(1, len(arr)):
            if arr[i] > cur:
                cur = arr[i]
                win = 0
            win += 1
            if (win == k): break
        return cur

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        cnt = 0
        a = arr
        i = 0
        n = len(a)
        for j in range(1, n):
            if a[i] > a[j]:
                cnt += 1
            else:
                i = j
                cnt = 1
            if cnt >= k:
                return a[i]
        return a[i]

class Solution:
    def getWinner(self, arr, k):
        maxval = max(arr)
        l = len(arr)
        if k >= l-1: return maxval
        win = False
        while True:
            if win: local_max = max(arr[:k])
            else: local_max = max(arr[:k+1])
            # print(\"local_max: \",local_max)
            if local_max == arr[0]: return local_max
            else:
                win = True
                index = arr.index(local_max)
                # print(\"index: \",index)
                arr = arr[index:] + arr[:index]
                # print(arr)


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if len(arr) < k:
            return max(arr)
        count = collections.Counter(arr)
        inc = 1
        while True:
            winner = arr[0]
            if arr[0] < arr[1]:
                temp = arr[0]
                arr[0] = arr[1]
                arr[1] = temp
                winner = arr[0]
            temp = arr[1+inc]
            arr[1+inc] = arr[1]
            arr[1] = temp
            inc = (inc+1)%(len(arr)-1)
            count[winner]+=1
            if count[winner] == k+1:
                return winner
            


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        winCnt = 0
        win = 0
        for i in range(1, len(arr)):
            if arr[i] < arr[win]:
                winCnt += 1
            else:
                winCnt = 1
                win = i
            if winCnt >= k:
                return arr[win]
        return arr[win]


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        
        if k >= n - 1:
            return max(arr)
        
        winner, win_count = None, 0
        
        c = 0
        
        while win_count < k:
            # play challenge
            
            p1, p2 = arr[c], arr[(c + 1) %n]
            
            w, l = max(p1, p2), min(p1, p2)
            
            if winner == w:
                win_count += 1
            else:
                winner, win_count = w, 1
                
            arr[c], arr[(c + 1) % n] = l, w
            c = (c + 1) % n
            
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        array_length = len(arr)
        if k > array_length:
            return max(arr)
        index_one = 0
        index_two = 1
        wins = 0
        while index_two < array_length:
            if index_one == index_two:
                index_two += 1
                if index_two == array_length:
                    break
            # greater than
            if arr[index_one] > arr[index_two]:
                wins += 1 
                if wins == k:
                    return arr[index_one]
                index_two += 1
                continue
            # less than
            index_one += 1
            index_two = index_one - 1
            wins = 0

        return max(arr)  



class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        if k>=len(arr): return max(arr)
        winner=arr[0]
        c=collections.Counter()
        for i in arr[1:]:
            winner=max(winner,i)
            c[winner]+=1
            if c[winner]==k: return winner
        return winner

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        residual_list = arr
        filled_list = []
        winner_dict = {}
        residual_dict = []
        
        if k>=len(arr):
            return max(arr)
        
        for item in residual_list:
            filled_list.append(item)
            if len(filled_list)>=2:
                l1 = filled_list[0]
                l2 = filled_list[1]
                winner = max(l1,l2)
                if winner in winner_dict:
                    winner_dict[winner]+=1
                else:
                    winner_dict[winner] = 1
                if winner_dict[winner]==k:
                    return winner
                filled_list.remove(min(l1,l2))
                residual_list.append(min(l1,l2))
            else:
                continue


class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        ki=0
        best=arr[0]
        for i in range(1,len(arr)):
            if arr[i]<best:
                ki+=1
            else:
                best=arr[i]
                ki=1
            if ki==k:
                return best
        return best