<p>A competition consists of <code>n</code> players numbered from <code>0</code> to <code>n - 1</code>.</p>

<p>You are given an integer array <code>skills</code> of size <code>n</code> and a <strong>positive</strong> integer <code>k</code>, where <code>skills[i]</code> is the skill level of player <code>i</code>. All integers in <code>skills</code> are <strong>unique</strong>.</p>

<p>All players are standing in a queue in order from player <code>0</code> to player <code>n - 1</code>.</p>

<p>The competition process is as follows:</p>

<ul>
	<li>The first two players in the queue play a game, and the player with the <strong>higher</strong> skill level wins.</li>
	<li>After the game, the winner stays at the beginning of the queue, and the loser goes to the end of it.</li>
</ul>

<p>The winner of the competition is the <strong>first</strong> player who wins <code>k</code> games <strong>in a row</strong>.</p>

<p>Return the initial index of the <em>winning</em> player.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">skills = [4,2,6,3,9], k = 2</span></p>

<p><strong>Output:</strong> 2</p>

<p><strong>Explanation:</strong></p>

<p>Initially, the queue of players is <code>[0,1,2,3,4]</code>. The following process happens:</p>

<ul>
	<li>Players 0 and 1 play a game, since the skill of player 0 is higher than that of player 1, player 0 wins. The resulting queue is <code>[0,2,3,4,1]</code>.</li>
	<li>Players 0 and 2 play a game, since the skill of player 2 is higher than that of player 0, player 2 wins. The resulting queue is <code>[2,3,4,1,0]</code>.</li>
	<li>Players 2 and 3 play a game, since the skill of player 2 is higher than that of player 3, player 2 wins. The resulting queue is <code>[2,4,1,0,3]</code>.</li>
</ul>

<p>Player 2 won <code>k = 2</code> games in a row, so the winner is player 2.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">skills = [2,5,4], k = 3</span></p>

<p><strong>Output:</strong> 1</p>

<p><strong>Explanation:</strong></p>

<p>Initially, the queue of players is <code>[0,1,2]</code>. The following process happens:</p>

<ul>
	<li>Players 0 and 1 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is <code>[1,2,0]</code>.</li>
	<li>Players 1 and 2 play a game, since the skill of player 1 is higher than that of player 2, player 1 wins. The resulting queue is <code>[1,0,2]</code>.</li>
	<li>Players 1 and 0 play a game, since the skill of player 1 is higher than that of player 0, player 1 wins. The resulting queue is <code>[1,2,0]</code>.</li>
</ul>

<p>Player 1 won <code>k = 3</code> games in a row, so the winner is player 1.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == skills.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= skills[i] &lt;= 10<sup>6</sup></code></li>
	<li>All integers in <code>skills</code> are unique.</li>
</ul>

class SegmentTree:
    # merge(left, right): function used to merge the two halves
    # basef(value): function applied on individual values
    # basev: identity for merge function, merger(value, basev) = value
    # update(node_value, old, new): function to update the nodes
    def __init__(self, array, merge=lambda x,y:x>y, basef=lambda x:x, basev = 0):
        self.merge = merge
        self.basef = basef
        self.basev = basev
        self.n = len(array)
        self.array = array
        self.tree = [0] * ( 2**ceil(log2(len(array))+1) - 1 )
        self.build(array)
    
    def __str__(self):
        return ' '.join([str(x) for x in self.tree])

    def _build_util(self, l, r, i, a):
        if(l==r):
            self.tree[i] = self.basef(a[l])
            return self.tree[i]
        mid = (l+r)//2
        self.tree[i] = self.merge(self._build_util(l,mid, 2*i+1, a), self._build_util(mid+1, r, 2*i+2, a))
        return self.tree[i]

    def build(self, a):
        self._build_util(0, len(a)-1, 0, a)

    def _query_util(self, i, ln, rn, l, r):
        if ln>=l and rn<=r:
            return self.tree[i]
        if ln>r or rn<l:
            return self.basev
        return self.merge( self._query_util( 2*i+1, ln, (ln+rn)//2, l, r ), self._query_util( 2*i+2, (ln+rn)//2+1, rn, l, r ) )

    def query(self, l, r):
        return self._query_util( 0, 0, self.n-1, l, r )

    def _update_util(self, i, ln, rn, x, v):
        if x>=ln and x<=rn:
            if ln != rn:
                self._update_util( 2*i+1, ln, (ln+rn)//2, x, v )
                self._update_util( 2*i+2, (ln+rn)//2 + 1, rn, x, v )
                self.tree[i] = self.merge(self.tree[2*i+1], self.tree[2*i+2])
            else:
                self.tree[i] = self.basef(v)

    def update(self, x, v):
        self._update_util( 0, 0, self.n-1, x, v )   
        self.array[x] =v        


class Solution:
    def mergeSegment(self,x,y):
        return x if x > y else y

    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        n=len(skills)
        ar = [i for i in range(n)]
        sg = SegmentTree(skills,merge=self.mergeSegment)
        for i in range(n):
            start = max(0,i-1)
            end = n
            if ( i + k - 1) < n:
                start,end=0,0
                if i==0:
                    start=0
                    end=i+k
                else:
                    start=i-1
                    end=i+k-1
                if sg.query(start,end)==skills[i]:
                    return ar[i]
            else:
                start,end=0,n
                if start==0 and sg.query(start,end)==skills[i]:
                    return ar[i]
                elif start!=0:
                    start=i-1
                    end2=min(i,abs(n-i-k-1))
                    if skills[i]==max(sg.query(start,end),sg.query(0,end2)):
                        return ar[i]
                            
        return -1
1763