''' mbinary
#########################################################################
# File : winnerTree.py
# Author: mbinary
# Mail: zhuheqin1@gmail.com
# Blog: https://mbinary.xyz
# Github: https://github.com/mbinary
# Created Time: 2018-05-19  23:06
# Description:
#########################################################################
'''


class winnerTree:
    '''if i<lowExt    p = (i+offset)//2
       else           p = (i+n-1-lowExt)//2
       offset is a num 2^k-1 just bigger than n
        p is the index of tree
        i is the index of players
        lowExt is the double node num of the lowest layer of the tree
    '''

    def __init__(self, players, reverse=False):
        self.n = len(players)
        self.tree = [0] * self.n
        players.insert(0, 0)
        self.players = players
        self.reverse = reverse
        self.getNum()
        self.initTree(1)

    def getNum(self):
        i = 1
        while 2 * i < self.n:
            i = i * 2
        if 2 * i == self.n:
            self.lowExt = 0
            self.s = 2 * i - 1
        else:
            self.lowExt = (self.n - i) * 2
            self.s = i - 1
        self.offset = 2 * i - 1

    def treeToArray(self, p):
        return 2 * p - self.offset if p > self.s else 2 * p + self.lowExt - self.n + 1

    def arrayToTree(self, i):
        return (i + self.offset) // 2 if i <= self.lowExt else (
            i - self.lowExt + self.n - 1) // 2

    def win(self, a, b):
        return a < b if self.reverse else a > b

    def initTree(self, p):
        if p >= self.n:
            delta = p % 2  #!!! good job  notice delta mark the lchild or rchlid
            return self.players[self.treeToArray(p // 2) + delta]
        l = self.initTree(2 * p)
        r = self.initTree(2 * p + 1)
        self.tree[p] = l if self.win(l, r) else r
        return self.tree[p]

    def winner(self):
        idx = 1
        while 2 * idx < self.n:
            idx = 2 * idx if self.tree[2 *
                                       idx] == self.tree[idx] else idx * 2 + 1
        num = self.treeToArray(idx)
        num = num + 1 if self.players[num] != self.tree[1] else num
        return self.tree[1], num

    def getOppo(self, i, x, p):
        oppo = None
        if 2 * p < self.n: oppo = self.tree[2 * p]
        elif i <= self.lowExt: oppo = self.players[i - 1 + i % 2 * 2]
        else:
            lpl = self.players[2 * p + self.lowExt - self.n + 1]
            oppo = lpl if lpl != x else self.players[2 * p + self.lowExt -
                                                     self.n + 2]
        return oppo

    def update(self, i, x):
        ''' i is 1-indexed  which is the num of player
            and x is the new val of the player '''
        self.players[i] = x
        p = self.arrayToTree(i)
        oppo = self.getOppo(i, x, p)
        self.tree[p] = x if self.win(x, oppo) else oppo
        p = p // 2
        while p:
            l = self.tree[p * 2]
            r = None
            if 2 * p + 1 < self.n: r = self.tree[p * 2 + 1]  #notice this !!!
            else: r = self.players[2 * p + self.lowExt - self.n + 1]
            self.tree[p] = l if self.win(l, r) else r
            p = p // 2


if __name__ == '__main__':
    s = [4, 1, 6, 7, 9, 5234, 0, 2, 7, 4, 123]
    t = winnerTree(s)
    print(t.players, t.tree)
    for i in s:
        val, idx = t.winner()
        print(val, idx)
        t.update(idx, -1)
'''
[0, 4, 1, 6, 7, 9, 5234, 0, 2, 7, 4, 123] [0, 5234, 5234, 123, 7, 5234, 7, 123, 4, 7, 5234]
5234 6
123 11
9 5
7 4
7 9
6 3
4 1
4 10
2 8
1 2
'''