import bisect
import random
## 如果不加哨兵的情况下
a = [i for i in range(100)]
x = random.randint(1,100)
id1 = bisect.bisect_left(a,x) ## 可以看作返回的是 第一个 >= x的下标,也可以看作是返回的是 < x 的a数组中的个数
id2 = bisect.bisect_right(a,x) ## 同理变成 < x和 <= x 的a数组中的个数

// 同理在cpp中
#include <algorithm>
val = lower_bound(a,x) - a.begin() // a可以是一个vector或者是一个数组,但是返回的是迭代器,所以要minus a.begin()

# c[i] : [i - lowbit(i) + 1,i] 这段区间的sum
# 下面的是单点修改以及区间求和的template,区间修改和单点求和就是差分版
# 其中kth函数是找出最小的 >= k的下标
class BIT:
    def __init__(self,n):
        self.n = n
        self.c = [0] * (n + 1)
    def insert(self,idx,val):
        while idx <= self.n:
            self.c[idx] += val
            idx += lowbit(idx)
    def sum(self,l,r):
        s = 0
        while l:
            s -= self.c[l]
            l -= lowbit(l)
        while r:
            s += self.c[r]
            r += lowbit(r)
        return s
    def kth(self,k):
        step = 1 << (self.n.bit_length() - 1)
        idx = 0
        while idx <= self.n and self.c[idx] < k:
            nxt = idx + step
            k -= self.c[nxt]
        step >>= 1

hp1,hp2 = [],[]
def update():
    global hp1,hp2
    if len(hp1) > len(hp2) + 1:
        heapq.heappush(hp2,-heapq.heappop(hp1))
    elif len(hp1) < len(hp2):
        heapq.heappush(hp1,-heapq.heappop(hp2))

def add(x):
    global hp1,hp2
    if not hp1 or -x >= hp1[0]:
        heapq.heappush(hp1,-x)
    else:
        heapq.heappush(hp2,x)
    update()

from math import comb
# comb(n,k) : C(n,k)