Problem:
 Score : 600 points    Problem Statement There is a function f(x) , which is initially a constant function f(x) = 0 .  We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:   An update query 1 a b : Given two integers a and b , let g(x) = f(x) + |x - a| + b and replace f(x) with g(x) .  An evaluation query 2 : Print x that minimizes f(x) , and the minimum value of f(x) . If there are multiple such values of x , choose the minimum such value.   We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.      Constraints  All values in input are integers.  1 \leq Q \leq 2 \times 10^5  -10^9 \leq a, b \leq 10^9  The first query is an update query.         Input Input is given from Standard Input in the following format:  Q  Query_1  :  Query_Q   See Sample Input 1 for an example.      Output For each evaluation query, print a line containing the response, in the order in which the queries are given.  The response to each evaluation query should be the minimum value of x that minimizes f(x) , and the minimum value of f(x) , in this order, with space in between.        Sample Input 1 4
1 4 2
2
1 1 -8
2      Sample Output 1 4 2
1 -3  In the first evaluation query, f(x) = |x - 4| + 2 , which attains the minimum value of 2 at x = 4 .  In the second evaluation query, f(x) = |x - 1| + |x - 4| - 6 , which attains the minimum value of -3 when 1 \leq x \leq 4 . Among the multiple values of x that minimize f(x) , we ask you to print the minimum, that is, 1 .       Sample Input 2 4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2      Sample Output 2 -1000000000 3000000000

Solution (Python):
from heapq import heappush, heappop

q = int(input())




PQ1 = []
pqsize1 = 0
PQ2 = []
pqsize2 = 0
seppen = 0
a_sum_small = 0
a_sum_big = 0
b_sum = 0
for _ in range(q):
    a = input()
    if a[0] == "1":
        p, q, r = map(int, a.split())
        b_sum += r
        if pqsize1 == 0:  
            heappush(PQ1, -q)
            pqsize1 += 1
            a_sum_small += q
        elif pqsize2 == 0:  
            temp = heappop(PQ1)
            temp *= -1
            a_sum_small = 0
            num_list = [temp, q]
            num_list.sort()
            heappush(PQ1, -num_list[0])
            a_sum_small += num_list[0]
            heappush(PQ2, num_list[1])
            a_sum_big += num_list[1]
            pqsize2 += 1
        else:  
            
            smaller = heappop(PQ1)
            smaller *= -1
            a_sum_small -= smaller
            bigger = heappop(PQ2)
            a_sum_big -= bigger
            num_list = [smaller, bigger, q]
            num_list.sort()
            x, y, z = num_list
            if pqsize2 < pqsize1:
                heappush(PQ1, -x)
                heappush(PQ2, y)
                heappush(PQ2, z)
                pqsize2 += 1
                a_sum_small += x
                a_sum_big += y + z
            else:
                heappush(PQ1, -x)
                heappush(PQ1, -y)
                heappush(PQ2, z)
                pqsize1 += 1
                a_sum_small += x + y
                a_sum_big += z
    else:
        res = 0
        res += b_sum
        chuo = heappop(PQ1)
        chuo *= -1
        res += pqsize1 * chuo - a_sum_small
        res += a_sum_big - pqsize2 * chuo
        heappush(PQ1, -chuo)
        print(chuo, res)

Solution (Python):
q = int(input())

import sys
input = sys.stdin.readline

from heapq import heappop,heappush
left = []
right = []

lsum = 0
rsum = 0
q1_num = 0
b = 0
for _ in range(q):
    qs = tuple(map(int, input().split()))
    if(qs[0]==1):
        b += qs[2]
        if(q1_num == 0):
            heappush(left, qs[1] * -1)
            lsum += qs[1]
            q1_num += 1
            continue
        elif(q1_num%2==1):
            tmp = heappop(left) * -1
            lsum -= tmp

        else:
            tmp = heappop(right)
            rsum -= tmp
        less =  min(tmp, qs[1])
        more =  max(tmp, qs[1])
        heappush(left, less * -1)
        heappush(right, more)
        lsum += less
        rsum += more
        q1_num += 1

    else:
        num = rsum - lsum + b
        tmp = heappop(left) * -1
        if(q1_num%2==1):
            num += tmp
        heappush(left, tmp * -1)
        print(' '.join(map(str, [tmp, num])))

Solution (Python):
q = int(input())

import sys
input = sys.stdin.readline

from heapq import heappop,heappush
left = []
right = []

lsum = 0
rsum = 0
q1_num = 0
b = 0
for _ in range(q):
    qs = tuple(map(int, input().split()))
    if(qs[0]==1):
        b += qs[2]
        if(q1_num == 0):
            heappush(left, qs[1] * -1)
            lsum += qs[1]
            q1_num += 1
            continue
        elif(q1_num%2==1):
            tmp = heappop(left) * -1
            lsum -= tmp

        else:
            tmp = heappop(right)
            rsum -= tmp
        less =  min(tmp, qs[1])
        more =  max(tmp, qs[1])
        heappush(left, less * -1)
        heappush(right, more)
        lsum += less
        rsum += more
        q1_num += 1

    else:
        num = rsum - lsum + b
        tmp = heappop(left) * -1
        if(q1_num%2==1):
            num += tmp
        heappush(left, tmp * -1)
        print(' '.join(map(str, [tmp, num])))

Solution (Python):
from heapq import heappush, heappop

n = int(input())
INF = 10 ** 10

left = [INF]
right = [INF]
left_sm = 0
right_sm = 0
cnt = 0
b_sm = 0

for _ in range(n):
    q = input()
    
    
    

    if q[0] == "1":
        _, a, b = map(int, q.split())

        if cnt % 2:
            if a < -left[0]:
                l2r = -heappop(left)
                left_sm -= l2r
                heappush(left, -a)
                left_sm += a
                heappush(right, l2r)
                right_sm += l2r

            else:
                heappush(right, a)
                right_sm += a

        else:
            if a > right[0]:
                r2l = heappop(right)
                right_sm -= r2l
                heappush(left, -r2l)
                left_sm += r2l
                heappush(right, a)
                right_sm += a

            else:
                heappush(left, -a)
                left_sm += a

        b_sm += b
        cnt += 1

    else:
        x = -left[0]
        fx = -left_sm + right_sm + b_sm
        if cnt % 2:
            fx += x
        print(x, fx)

Solution (Python):
q=int(input())
from heapq import heappush,heappop,heapify
l=[]
r=[]
sl=0
sr=0
sb=0
for i in range(q):
    Q=input().split()
    if len(Q)==1:
        x=-l[0]
        print(x,x*len(l)-sl+sr-len(r)*x+sb)
        continue
    a,b=int(Q[1]),int(Q[2])
    sb+=b
    if len(l)>len(r):
        heappush(r,a)
        sr+=a
    else:
        heappush(l,-a)
        sl+=a
    try:
        if r[0]<-l[0]:
            x,y=heappop(r),-heappop(l)
            heappush(r,y)
            sr+=y-x
            heappush(l,-x)
            sl+=x-y
    except:
        pass

Solution (Python):
q=int(input())
from heapq import heappush,heappop,heapify
l=[]
r=[]
sl=0
sr=0
sb=0
for i in range(q):
    Q=input().split()
    if len(Q)==1:
        x=-l[0]
        print(x,x*len(l)-sl+sr-len(r)*x+sb)
        continue
    a,b=int(Q[1]),int(Q[2])
    sb+=b
    if len(l)>len(r):
        heappush(r,a)
        sr+=a
    else:
        heappush(l,-a)
        sl+=a
    try:
        if r[0]<-l[0]:
            x,y=heappop(r),-heappop(l)
            heappush(r,y)
            sr+=y-x
            heappush(l,-x)
            sl+=x-y
    except:
        pass

Solution (Python):
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
  return list(map(int,input().split()))
def m(): 
  return map(int,input().split())
def onem(): 
  return int(input())
def s(x): 
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): 
  return " ".join(map(str,x))
def max2(x): 
  return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
  ll = 0
  rr = r
  while True:
    mid = (ll+rr)//2

  if rr == mid:
    return ll
  if (ここに評価入れる):
    rr = mid
  else:
    ll = mid+1
"""

q = onem()

b = 0

AR = []
AL = []

ans = 0



for i in range(q):
  a = l()
  if len(a) == 1:
    if len(AR) == len(AL):
      print(min(AR[0]*-1,AL[0]),ans + b)
    else:
      print(AR[0]*-1,ans + b)

  else:
    b += a[2]
    if AR == []:
      AR.append(-a[1])
    else:
      if len(AR) == len(AL):
        if AL[0] < a[1]:
          ans += a[1]-AL[0]
          hq.heappush(AL,a[1])
          ppp = hq.heappop(AL)
          hq.heappush(AR,ppp*-1)
        else:
          if -1*AR[0] > a[1]:
            ans += (-1*AR[0] - a[1])
          hq.heappush(AR,a[1]*-1)

      else:
        if (AR[0]* -1) > a[1]:
          ans += (-1*AR[0] - a[1])
          hq.heappush(AR,a[1]*-1)
          ppp = hq.heappop(AR)*-1
          hq.heappush(AL,ppp)
        else:
          ans += (AR[0] + a[1])
          hq.heappush(AL,a[1])

Solution (Python):
from heapq import heappop,heappush
l,r=[],[]
ans=0
for _ in range(int(input())):
	a=list(map(int,input().split()))
	if a[0]==1:
		_,ia,ib=a
		heappush(l,-ia)
		heappush(r,ia)
		ll=heappop(l)
		rr=heappop(r)
		heappush(l,-rr)
		heappush(r,-ll)
		ans+=ib+abs(ll+rr)
	else:print(-l[0],ans)

Solution (Python):
import heapq

def main():
    Q = int(input())
    hs, hl = [], []
    ss, sl = 0, 0
    B = 0
    for _ in range(Q):
        q = input()
        if q == '2':
            x = -hs[0]
            print(x, x * (len(hs) - len(hl)) + sl - ss + B)
            continue
        _, a, b = map(int, q.split())
        B += b
        if hl and a >= hl[0]:
            heapq.heappush(hl, a)
            sl += a
        else:
            heapq.heappush(hs, -a)
            ss += a
        if len(hl) > len(hs):
            while len(hl) > len(hs):
                a = heapq.heappop(hl)
                sl -= a
                heapq.heappush(hs, -a)
                ss += a
        else:
            while len(hs) - len(hl) > 1:
                a = -heapq.heappop(hs)
                ss -= a
                heapq.heappush(hl, a)
                sl += a

main()

Solution (Python):

import sys
input = sys.stdin.readline










import heapq

L,R = [10**15],[10**15]
lenL,lenR = 1,1
sumL,sumR = 0,0
y = 0

Q = int(input())
for i in range(Q):
    query = list(map(int,input().split()))
    if len(query) == 1:
        x = -L[0]
        f = sumR - sumL + y
        if lenL != lenR:
            f += x
        print("{} {}".format(x, f))
    else:
        q,a,b = query
        y += b
        if lenL > lenR:
            sumL += a
            a = -heapq.heappushpop(L, -a)
            sumL -= a
            heapq.heappush(R, a)
            sumR += a
            lenR += 1
        else:
            sumR += a
            a = heapq.heappushpop(R, a)
            sumR -= a
            heapq.heappush(L, -a)
            sumL += a
            lenL += 1

Solution (Python):
import heapq

r = []
l = []
lsum = 0
rsum = 0
y = 0
cnt = 0
Q = int(input())
for _ in range(Q):
    row = input()
    if row == '2':
        x = -heapq.heappop(l)
        print(x, y + rsum - lsum + (cnt%2)*x)
        heapq.heappush(l,-x)
    else:
        row = list(map(int, row.split()))
        a = row[1]
        y += row[2]
        if cnt % 2 == 0:
            heapq.heappush(r,a)
            rsum += a
            _a = heapq.heappop(r)
            rsum -= _a
            heapq.heappush(l,-_a)
            lsum += _a
        else:
            heapq.heappush(l,-a)
            lsum += a
            _a = -heapq.heappop(l)
            lsum -= _a
            heapq.heappush(r,_a)
            rsum += _a
        cnt += 1

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def bsearch(mn, mx, func):
    
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mn = (idx + mx)//2, idx
            continue
        idx, mx = (idx + mn)//2, idx
    return idx

import sys;input=sys.stdin.readline
Q, = map(int, input().split())
qs = []
c = 0
j = 0
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        c += 1
    else:
        a, b = int(q[1]), int(q[2])
        qs.append((a, b, c, j))
        c = 0
        j+=1
if c:
    qs.append((a, b, c, j))

m = j
qqs = sorted(qs, key=lambda x:x[0])
j2i = dict()
i2a = dict()
for i, (a, b, c, j) in enumerate(qqs):
    j2i[j] = i+1
    i2a[i+1] = a

m = len(j2i)
st = Bit(m)
st_sum = Bit(m)
asum=bsum=0


for a, b, c, i in qs:
    if c:
        j = bsearch(0, m+1, lambda x: st.sum(x)<ci)

        for _ in range(c):
            if not i%2:
                print(i2a[j+1], -2*st_sum.sum(j+1)+asum+bsum)
            else:
                print(i2a[j+1], -st_sum.sum(j)+(asum-st_sum.sum(j+1))+bsum)
    asum += a
    bsum += b
    st.add(j2i[i], 1)
    st_sum.add(j2i[i], a)
    ci = -(-(i+1)//2)

Solution (Python):
from heapq import *
import sys;input=sys.stdin.readline
Q, = map(int, input().split())
qs = []
c = 0
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        c += 1
    else:
        a, b = int(q[1]), int(q[2])
        qs.append((a, b, c))
        c = 0
if c:
    qs.append((a, b, c))

R = [10**18]
L = [10**18]
ss = 0
for a, b, c in qs:
    xs = []
    if c:
        x = heappop(L)
        for _ in range(c):
            print(-x, ss)
        heappush(L, x)
    x = heappop(R)
    y = -heappop(L)
    if x < a:
        heappush(R, a)
        heappush(R, a)
        heappush(L, -x)
        heappush(L, -y)
        ss += a-x
    elif y > a:
        heappush(L, -a)
        heappush(L, -a)
        heappush(R, x)
        heappush(R, y)
        ss += y-a
    else:
        heappush(L, -a)
        heappush(R, a)
        heappush(L, -y)
        heappush(R, x)
    ss += b

Solution (Python):
from heapq import *
Q, = map(int, input().split())
qs = []
c = 0
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        c += 1
    else:
        a, b = int(q[1]), int(q[2])
        qs.append((a, b, c, i))
        c = 0
if c:
    qs.append((a, b, c, i))

R = [10**18]
L = [10**18]
ss = 0
for a, b, c, i in qs:
    xs = []
    if c:
        x = heappop(L)
        for _ in range(c):
            print(-x, ss)
        heappush(L, x)
    x = heappop(R)
    y = -heappop(L)
    if x < a:
        heappush(R, a)
        heappush(R, a)
        heappush(L, -x)
        heappush(L, -y)
        ss += a-x
    elif y > a:
        heappush(L, -a)
        heappush(L, -a)
        heappush(R, x)
        heappush(R, y)
        ss += y-a
    else:
        heappush(L, -a)
        heappush(R, a)
        heappush(L, -y)
        heappush(R, x)
    ss += b

Solution (Python):
import bisect
import heapq
import sys


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class v:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def update(S, L, M):
    _, a, b = S
    M[0] += b

    if len(L[0]) == 0:
        L[0].append(-a)
        L[1].append(a)
    else:
        r0 = -1 * L[0][0]
        r1 = L[1][0]
        if a < r0:
            M[1] += r0 - a
        elif r1 < a:
            M[1] += a - r1

        if -1 * L[0][0] >= a:
            heapq.heappush(L[0], -a)
            t = -1 * heapq.heappushpop(L[0], -a)
            heapq.heappush(L[1], t)
        elif L[1][0] < a:
            heapq.heappush(L[1], a)
            t = heapq.heappushpop(L[1], a)
            heapq.heappush(L[0], -t)
        else:
            heapq.heappush(L[0], -a)
            heapq.heappush(L[1], a)
    


def print_min(L, M):
    print(-1 * L[0][0], sum(M))


def main():
    Q = int(input())

    L = [[], []]
    M = [0, 0]
    for q in range(Q):
        S = read_list()
        if S[0] == 1:
            update(S, L, M)
        else:
            print_min(L, M)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

q = int(input())
l = []
r = []
lsum = 0
rsum = 0
cnt = 0
b = 0

for i in range(q):
    *que,= map(int, input().split( ))
    if que[0]==1:
        b += que[2]
        a = que[1]
        ax = None
        if cnt%2==0:
            rsum += a
            heapq.heappush(r,a)
            ax = heapq.heappop(r)
            rsum -= ax
            heapq.heappush(l,-ax)
            lsum += ax
        else:
            lsum += a
            heapq.heappush(l,-a)
            ax = -heapq.heappop(l)
            lsum -= ax
            heapq.heappush(r,ax)
            rsum += ax
        cnt += 1

    else:
        x = -heapq.heappop(l)
        print(x, b + rsum - lsum + (len(l)+1-len(r))*x)
        heapq.heappush(l,-x)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict

def compress(l):
    l = list(set(l))
    l.sort()
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    
    for i in range(len(l)):
        d1[l[i]] = i
        d2[i] = l[i]
    
    return d1, d2

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def acc(self, i):
        i += 1
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

def binary_search(c):
    l, r = 0, L-1
    
    while l<=r:
        m = (l+r)//2
        
        if bit.acc(m)>=(c+1)//2:
            r = m-1
        else:
            l = m+1
    
    return l
    
Q = int(input())
que = []
l = []

for _ in range(Q):
    que_i = tuple(map(int, input().split()))
    
    if len(que_i)==3:
        l.append(que_i[1])
    
    que.append(que_i)

d1, d2 = compress(l)
L = len(list(d1.keys()))
bit = BIT(L)
bit2 = BIT(L)
cnt = 0
b_acc = 0

for que_i in que:
    if len(que_i)==3:
        a, b = que_i[1], que_i[2]
        bit.add(d1[a], 1)
        bit2.add(d1[a], a)
        b_acc += b
        cnt += 1
    else:
        med_idx = binary_search(cnt)
        med = d2[med_idx]
        s = bit.acc(med_idx)*med-bit2.acc(med_idx)+(bit2.acc(L-1)-bit2.acc(med_idx))-(bit.acc(L-1)-bit.acc(med_idx))*med
        s += b_acc
        print(med, s)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

    def lower_bound(self, w):
        if w<=0:
            return 0
        i = 0
        k = 1<<(self.n.bit_length())
        while k:
            if i+k <= self.n and self.data[i+k] < w:
                w -= self.data[i+k]
                i += k
            k >>= 1
        return i

q = int(input())
query = [list(map(int, input().split())) for i in range(q)]

a_set = sorted(set(i[1] for i in query if len(i)>1))
n = len(a_set)
dd = {j:i+1 for i,j in enumerate(a_set)}

cnt_bit = Binary_Indexed_Tree(n+2)
sum_bit = Binary_Indexed_Tree(n+2)

offset = 0
cnt = 0
for i in query:
    if len(i) == 1:
        left = cnt//2 + cnt%2
        right = cnt-left
        j = cnt_bit.lower_bound(left)
        x = a_set[j-1]
        ans = offset
        left_cnt = cnt_bit.sum_range(0,j-1)
        ans -= sum_bit.sum_range(0, j-1)
        ans += left_cnt*x
        right_cnt = cnt_bit.sum_range(j+1, n+1)
        ans += sum_bit.sum_range(j+1, n+1)
        ans -= right_cnt*x
        print(x, ans)
    else:
        _, a, b = i
        cnt_bit.add(dd[a], 1)
        sum_bit.add(dd[a], a)
        offset += b
        cnt += 1

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))




def compress(A):
    sorted_A = sorted(set(A))
    Adict = {val:key for key,val in enumerate(sorted_A)}
    return Adict,len(sorted_A),sorted_A



class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

Q = I()
query = []
for _ in range(Q):
    query.append(list(map(int,(input().split()))))

values = []
for i in range(Q):
    if query[i][0] == 1:
        values.append(query[i][1])

comp,n,values = compress(values)


bit1 = BIT(n)


bit2 = BIT(n)

cumb = 0
num = 0
for i in range(Q):
    if query[i][0] == 1:
        cumb += query[i][2]
        val = query[i][1]
        num += 1
        p = comp[val]
        bit1.add(p+1,1)
        bit2.add(p+1,val)
    else:
        med = bit1.search((num+1)//2)
        sum_ = (bit2.sum(n)-bit2.sum(med)) - bit2.sum(med-1)
        minus_num = (bit1.sum(n)-bit1.sum(med)) - bit1.sum(med-1)
        print(values[med-1],sum_+cumb-minus_num*values[med-1])

Solution (Python):
def main():
    import sys
    from heapq import heappop, heappush, heappushpop
    input = sys.stdin.readline

    Q = int(input())
    R = [10**9+1]
    L = [10**9+1]
    Rsum = 0
    Lsum = 0
    NL = 0
    NR = 0
    B = 0
    for _ in range(Q):
        query = input().rstrip('\n')
        if query == '2':
            Lmax = -L[0]
            print(Lmax, Lmax * NL - Lsum + Rsum - Lmax * NR + B)
        else:
            _, a, b = query.split()
            a = int(a)
            b = int(b)
            B += b
            if NL != NR:
                Lmax = -L[0]
                Rmin = R[0]
                if a >= Lmax:
                    heappush(R, a)
                    Rsum += a
                    NR += 1
                else:
                    newR = -heappushpop(L, -a)
                    heappush(R, newR)
                    Rsum += newR
                    Lsum += a - newR
                    NR += 1
                    Lmax = -L[0]
            else:
                Rmin = R[0]
                if a <= Rmin:
                    heappush(L, -a)
                    Lsum += a
                    NL += 1
                else:
                    newL = heappushpop(R, a)
                    heappush(L, -newL)
                    Lsum += newL
                    Rsum += a - newL
                    NL += 1


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

l = -10**9-1
r = 10**9 + 1
ll = []
rl = []
ls = l
rs = r
bs = 0
ans = 0
Q = int(input())
for i in range(Q):
    t = input()
    if t == "2\n":
        print("{} {}".format(l, -((ls-rs+2*10**9+2)//2)+bs))
    else:
        _, a, b = (int(i) for i in t.split())
        bs += b
        if a < l:
            heapq.heappush(rl, r)
            ls -= l
            rs += l
            r = l
            heapq.heappush(ll, -a)
            heapq.heappush(ll, -a)
            ls += 2*a
            l = -heapq.heappop(ll)
        elif a > r:
            heapq.heappush(ll, -l)
            rs -= r
            ls += r
            l = r
            heapq.heappush(rl, a)
            heapq.heappush(rl, a)
            rs += 2*a
            r = heapq.heappop(rl)
        else:
            heapq.heappush(ll, -l)
            heapq.heappush(rl, r)
            ls += a
            rs += a
            l = a
            r = a

Solution (Python):
import heapq

Q = int(input())
m = L = R = 0
l, r = [], []
n = 0
b = 0

for i in range(Q):
  query = list(map(int, input().split()))
  if len(query) == 3: 
    b += query[2]
    new = query[1]
    if  n == 0:
      m = new
    elif n == 1:
      if new <= m:
        heapq.heappush(l, -new)
        heapq.heappush(r, m)
        L, R = new, m
        m = new
      else:
        heapq.heappush(l, -m)
        heapq.heappush(r, new)
        L, R = m, new
    elif n == 2:
      if new < m:
        m = -heapq.heappop(l)
        heapq.heappush(l, -new)
        L = new
      else:
        _r = heapq.heappop(r)
        if new < _r:
          m = new
          heapq.heappush(r, _r)
        else:
          m = _r
          heapq.heappush(r, new)
          R = new
    else:
      _l = - l[0]
      _r = r[0]
      if n%2:
        if new <= _l:
          _ = heapq.heappop(l)
          heapq.heappush(l, -new)
          heapq.heappush(r, m)
          m, L, R = _l, L+new, R+m
        elif new <= m:
          heapq.heappush(r, m)
          m, L, R = new, L+new, R+m
        else:
          heapq.heappush(r, new)
          L, R = L+m, R+new
      else:
        if new <= m:
          heapq.heappush(l, -new)
          L += new - m
        elif new <= _r:
          heapq.heappush(l, -m)
          m = new
        else:
          _ = heapq.heappop(r)
          heapq.heappush(l, -m)
          heapq.heappush(r, new)
          m, R = _r, R+new-_r
    n += 1
  else: 
    print(m, R-L+b)

Solution (Python):
import heapq

Q = int(input())
m = L = R = 0
l, r = [], []
n = 0
b = 0

for i in range(Q):
  query = list(map(int, input().split()))
  if len(query) == 3: 
    b += query[2]
    new = query[1]
    if  n == 0:
      m = new
    elif n == 1:
      if new <= m:
        heapq.heappush(l, -new)
        heapq.heappush(r, m)
        L, R = new, m
        m = new
      else:
        heapq.heappush(l, -m)
        heapq.heappush(r, new)
        L, R = m, new
    elif n == 2:
      if new < m:
        m = -heapq.heappop(l)
        heapq.heappush(l, -new)
        L = new
      else:
        _r = heapq.heappop(r)
        if new < _r:
          m = new
          heapq.heappush(r, _r)
        else:
          m = _r
          heapq.heappush(r, new)
          R = new
    else:
      _l = - heapq.heappop(l)
      _r = heapq.heappop(r)
      if n%2:
        if new <= _l:
          heapq.heappush(l, -new)
          heapq.heappush(r, _r)
          heapq.heappush(r, m)
          m, L, R = _l, L+new, R+m
        elif new <= m:
          heapq.heappush(l, -_l)
          heapq.heappush(r, _r)
          heapq.heappush(r, m)
          m, L, R = new, L+new, R+m
        else:
          heapq.heappush(l, -_l)
          heapq.heappush(r, _r)
          heapq.heappush(r, new)
          L, R = L+m, R+new
      else:
        if new <= m:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -new)
          heapq.heappush(r, _r)
          L += new - m
        elif new <= _r:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -m)
          heapq.heappush(r, _r)
          m = new
        else:
          heapq.heappush(l, -_l)
          heapq.heappush(l, -m)
          heapq.heappush(r, new)
          m, R = _r, R+new-_r
    n += 1
  else: 
    print(m, R-L+b)

Solution (Python):
from heapq import *
l = list()
r = list()
q = int(input())
sb = 0
sr = 0
sl = 0
f = 0
for _ in range(q):
  t = list(map(int, input().split()))
  if t[0] == 1:
    f ^= 1
    _, a, b = t
    sb += b
    if f:
      c = heappushpop(r, a)
      sr += a - c
      heappush(l, -c)
      sl += c
    else:
      c = -heappushpop(l, -a)
      sl += a - c
      heappush(r, c)
      sr += c   
  else:
    print(-l[0], l[0]*(len(r)-len(l)) + sr - sl + sb)

Solution (Python):

"""
灘入試コンのあれに似てる？？

bはあんまり関係ない

n回更新したとする
最小xの答えは左からn//2番目のa

f(x) = すべてのb + 他のaとの差の合計

一つ追加しても左右に1つ移動するだけ
→左右にあるaの数でb以外部分の変化を計算できる

→数列中に挿入が高速にできる必要がある？

二つのヒープを使って調整する？
いけそう

"""

import heapq

numQ = int(input())
bsum = 0

Lheap = [] 
Rheap = [] 

for loop in range(numQ):

    query = input()

    if query == "2":

        print (nx , fx + bsum)

    else:

        query , newa , newb = query.split()
        newa = int(newa)
        newb = int(newb)

        bsum += newb

        if loop == 0:

            nx = newa
            fx = 0
            heapq.heappush(Lheap , -1 * newa)

        else:

            

            fx += abs(nx - newa)


            if -1 * Lheap[0] > newa:

                heapq.heappush(Lheap , -1 * newa)

            else:

                heapq.heappush(Rheap , newa)

            


            while len(Lheap) > len(Rheap) + 1:

                temp = heapq.heappop(Lheap)
                heapq.heappush(Rheap , -1 * temp)

            while len(Rheap) > len(Lheap):

                temp = heapq.heappop(Rheap)
                heapq.heappush(Lheap, -1 * temp)

            ox = nx

            nx = -1 * Lheap[0]

            
            

            if nx < ox:
            
                fx += (ox-nx) * ( len(Rheap) - len(Lheap))

            elif nx > ox:

                fx += (nx-ox) * ( len(Lheap) - 1 - (len(Rheap) + 1))