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):

import heapq
import sys

buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(Q):
    sb = 0

    l = []
    r = []
    sl = 0
    sr = 0

    for q in Q:
        if q[0] == 1:
            _, a, b = q
            heapq.heappush(l, -a)
            sl += a

            if len(l) > len(r) + 1:
                a = -heapq.heappop(l)
                heapq.heappush(r, a)
                sl -= a
                sr += a

            while l and r and -l[0] > r[0]:
                a = -heapq.heappop(l)
                heapq.heappush(r, a)
                sl -= a
                sr += a

                a = heapq.heappop(r)
                heapq.heappush(l, -a)
                sl += a
                sr -= a

            sb += b
        else:
            x = -l[0]
            print(x, abs(sl - len(l)*x) + abs(sr - len(r)*x) + sb)

def main():
    N = read_int()
    Q = [read_int_n() for _ in range(N)]
    slv(Q)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
Q=int(input())

alist=[]
hq_left,hq_right=[],[]
dummy,a1,b1=map(int,input().split())
heapq.heappush(hq_left,-a1)
heapq.heappush(hq_right,a1)
b=b1

min_arg=-hq_left[0]
min_diff=0

for _ in range(Q-1):
  query=list(map(int,input().split()))
  if len(query)==3:    
    dummy,ai,bi=query
    b+=bi
    
    max_left=-hq_left[0]
    min_right=hq_right[0]
    if ai<max_left:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_left,-ai)
      heapq.heappop(hq_left)
      heapq.heappush(hq_right,max_left)      
      min_diff+=max_left-ai
    elif min_right<ai:
      heapq.heappush(hq_right,ai)
      heapq.heappush(hq_right,ai)
      heapq.heappop(hq_right)
      heapq.heappush(hq_left,-min_right)      
      min_diff+=ai-min_right
    else:
      heapq.heappush(hq_left,-ai)
      heapq.heappush(hq_right,ai)      
  else:    
    min_arg=-hq_left[0]
    min_value=min_diff+b
    print(min_arg,min_value)

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

import heapq

Q = int(input())

ans = 0

INF = 10 ** 18

L_pque = []
R_pque = []

heapq.heappush(L_pque, +INF)
heapq.heappush(R_pque, +INF)

for _ in range(Q):
    tmp = tuple(map(str, input().split()))
    if len(tmp) == 1:
        print (-L_pque[0], ans)
    else:
        a = int(tmp[1])
        b = int(tmp[2])

        ans += b

        tmpA = -L_pque[0]
        tmpB = +R_pque[0]
        

        if a < tmpA:
            ans += abs(tmpA - a)
        elif tmpB < a:
            ans += abs(a - tmpB)
        
        heapq.heappush(L_pque, -a)
        heapq.heappush(R_pque, +a)

        tmpA = -heapq.heappop(L_pque)
        tmpB = +heapq.heappop(R_pque)

        if tmpA <= tmpB:
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)
        else:
            tmpA, tmpB = tmpB, tmpA
            heapq.heappush(L_pque, -tmpA)
            heapq.heappush(R_pque, +tmpB)

Solution (Python):
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

def main():
    Left = [10**10] 
    Right = [10**10]
    queri_num = 0 
    const = 0
    min_val = 0

    """
    [a1, a2, ..., ai]の中央値を高速に求めないといけない所で分からず諦めた。。。

    発想は単純で、左側パートと右側パートを分けて管理しておいて、新しいクエリが来るごとに
    aを左に入れるか右に入れるか決めれば良い。
    ただし左右のパートをリストで管理するとaの挿入にO(N)かかってしまうので、ここでは
    ヒープによって管理する。なので挿入はO(logN)で可能。

    あと中央値における関数の最小値も求めないといけないが、これは基本的には単に|a - median|
    増えるだけなので、これもaの挿入時に逐次O(1)で決定可能。
    """

    Q = int(input())
    for _ in range(Q):
        queri = list(map(int, input().split()))
        if queri[0] == 2:
            x = -heappop(Left)
            print("{} {}".format(x, min_val + const))
            heappush(Left, -x)
        elif queri_num == 1:
            queri_num = 0
            const += queri[2]
            a = queri[1]
            mid = -heappop(Left)
            if a < mid:
                min_val += mid - a
                heappush(Left, -a)
                heappush(Right, mid)
            else:
                min_val += a - mid
                heappush(Left, -mid)
                heappush(Right, a)
        elif queri_num == 0:
            queri_num = 1
            const += queri[2]
            a = queri[1]
            left = -heappop(Left)
            right = heappop(Right)
            if a < left:
                min_val += left - a
                heappush(Left, -a)
                heappush(Left, -left)
                heappush(Right, right)
            elif a < right:
                
                heappush(Left, -left)
                heappush(Left, -a)
                heappush(Right, right)
            else:
                min_val += a - right
                heappush(Left, -left)
                heappush(Left, -right)
                heappush(Right, a)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq

q = int(input())

nchange = 0
ming, maxg = [], []
heapq.heapify(ming)
heapq.heapify(maxg)
a = 0
b = 0
for i in range(q):
    qi = input()
    if qi[0] == '1':
        _, ai, bi = map(int, qi.split())
        b += bi
        nchange += 1
        if nchange % 2 == 1:
            if nchange == 1:
                x = ai
                continue
            Smax = -heapq.heappop(ming)
            Dmin = heapq.heappop(maxg)
            if Smax <= ai and ai <= Dmin:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, Dmin)
                x = ai
            elif ai < Smax:
                heapq.heappush(ming, -ai)
                heapq.heappush(maxg, Dmin)
                x = Smax
                a += Smax - ai
            else:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, ai)
                x = Dmin
                a += ai - Dmin
        else:
            heapq.heappush(ming, -min(x, ai))
            heapq.heappush(maxg, max(x, ai))
            a += abs(x - ai)
            x = -heapq.heappop(ming)
            heapq.heappush(ming, -x)
    else:
        print(x, a+b)

Solution (Python):
from heapq import heappop,heappush
q=int(input())
queries=[list(map(int,input().split()))for _ in range(q)]
l=[]
r=[]
ans=0
quecount=0
for query in queries:
  if query[0]==1:
    quecount+=1
    _,a,b=query
    ans+=b
    if quecount==1:
      mid=a
    elif quecount%2==1:
      if a<-l[0]:
        mid=-heappop(l)
        heappush(l,-a)
      elif r[0]<a:
        mid=heappop(r)
        heappush(r,a)
      else:
        mid=a
      ans+=abs(a-mid)
    else:
      ans+=abs(a-mid)
      heappush(l,-min(a,mid))
      heappush(r,max(a,mid))
  if query[0]==2:
    if quecount%2==1:
      ansind=mid
    else:
      ansind=-l[0]
    print(ansind,ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    q=int(input())
    Q=[tuple(map(int, input().split())) for _ in range(q)]
    asum=bsum=0
    from heapq import heappop, heappush
    s,l=[],[]
    mn=0
    for query in Q:
        if query[0]==1:
            a,b=query[1],query[2]
            bsum+=b
            E=[a,a]
            smx,lmn=a,a
            if s:
                smx=-heappop(s)
                E.append(smx)
            if l:
                lmn=heappop(l)
                E.append(lmn)
            if a<smx: mn+=smx-a
            elif lmn<a: mn+=a-lmn
            E.sort()
            for i in range(len(E)//2):
                heappush(s,-E[i])
                heappush(l,E[-1-i])
        else:
            print(-s[0], mn + bsum)

if __name__ == '__main__':
    main()

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

def main():
    Q = int(input())
    ans = 0
    l = []
    r = []
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            ans += query[2]
            heapq.heappush(l, -query[1])
            heapq.heappush(r, query[1])
            if -l[0] > r[0]:
                l_max = -1 * heapq.heappop(l)
                r_min = heapq.heappop(r)
                ans += abs(l_max-r_min)
                heapq.heappush(l, -r_min)
                heapq.heappush(r, l_max)

        else:
            print(-l[0],ans)






if __name__ == "__main__":
    main()

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

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)
    
    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    
    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

Q = int(input())
que = []
vals = []

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

idx = compress(vals)
rev_idx = defaultdict(int)

for k, v in idx.items():
    rev_idx[v] = k
    
N = len(list(idx.keys()))
bit1 = BIT(N)
bit2 = BIT(N)
b_acc = 0
cnt = 0

for i in range(Q):
    if len(que[i])==3:
        a, b = que[i][1], que[i][2]
        b_acc += b
        bit1.add(idx[a], 1)
        bit2.add(idx[a], a)
        cnt += 1
    else:
        l, r = 0, N-1
        
        while l<=r:
            m = (l+r)//2
            
            if bit1.acc(m+1)>=(cnt+1)//2:
                r = m-1
            else:
                l = m+1
        
        x = l
        lsum = bit1.acc(x)*rev_idx[x]-bit2.acc(x)
        rsum = bit2.acc(N)-bit2.acc(x)-(bit1.acc(N)-bit1.acc(x))*rev_idx[x]
        print(rev_idx[x], lsum+rsum+b_acc)

Solution (Python):
from heapq import heappop,heappush
q=int(input())
queries=[list(map(int,input().split()))for _ in range(q)]
l=[]
r=[]
ans=0
queonecount=0
mid=-1
for query in queries:
  if query[0]==1:
    queonecount+=1
    _,a,b=query
    ans+=b
    heappush(l,-a)
    heappush(r,a)
    midl=-heappop(l)
    midr=heappop(r)
    ans+=abs(midl-midr)
    heappush(l,-midr)
    heappush(r,midl)
  if query[0]==2:
    minind=-heappop(l)
    print(minind,ans)
    heappush(l,-minind)

Solution (Python):
import sys
import time
import heapq

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    import bisect
    q = int(input())
    left = PriorityQueue([-INF], desc=True)
    right = PriorityQueue([INF])
    const = 0
    cur_f = 0
    length = 0

    for _ in range(q):
        val = list(map(int, readline().split()))
        if val[0] == 1:
            length += 1
            new_a = val[1]
            const += val[2]
            l = left.top()
            r = right.top()
            cur_x = l
            if length % 2 == 1:
                if new_a < l:
                    right.push(left.top())
                    left.push(new_a)
                    cur_f += abs(l - new_a)
                elif new_a <= r:
                    left.push(new_a)
                    right.push(new_a)
                else:
                    left.push(right.top())
                    right.push(new_a)
                    cur_f += abs(r - new_a)
            else:
                if new_a < l:
                    left.pop()
                    left.push(new_a)
                    cur_f += abs(l - new_a)
                else:
                    right.pop()
                    right.push(new_a)
                    cur_f += abs(r - new_a)
        else:
            print(left.top(), cur_f + const)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    Q=int(input())
    Query=[]
    unique_a=set()
    for _ in range(Q):
        q=tuple(map(int,input().split()))
        if q[0]==1:
            unique_a.add(q[1])
            Query.append(q)
        else:
            Query.append((q[0],0,0))
    unique_a=list(unique_a)
    unique_a.sort()
    d={x:i for i,x in enumerate(unique_a)}
    b0=BIT(len(unique_a))
    b1=BIT(len(unique_a))
    sum_b=0
    sum_a=0
    c=0
    for i,(q,a,b) in enumerate(Query,1):
        if q==1:
            b0.add(d[a],1)
            b1.add(d[a],a)
            c+=1
            sum_a+=a
            sum_b+=b
        else:
            index,_=b0.lower_bound(-(-c//2))
            x=unique_a[index]
            tmp=b1.sum(index)
            z=b0.sum(index)
            y=(z*2-c)*x-tmp*2+sum_a+sum_b
            print(x,y)

if __name__ == '__main__':
    main()

Solution (Python):
import heapq

q = int(input())
l = []
r = []
ans = 0

for i in range(q):
    a = list(map(int,input().split()))
    if a[0] == 1:
        ans += a[2]
        if l == []:
            heapq.heappush(r,a[1])
            heapq.heappush(l,-a[1])
        else: 
            ll = -heapq.heappop(l)
            rr = heapq.heappop(r)
            if ll <= a[1] <= rr:
                heapq.heappush(r,rr)
                heapq.heappush(l,-ll) 
                heapq.heappush(r,a[1])
                heapq.heappush(l,-a[1]) 

            elif ll > a[1]:
                ans += ll-a[1]
                heapq.heappush(r,rr)
                heapq.heappush(r,ll) 
                heapq.heappush(l,-a[1])
                heapq.heappush(l,-a[1]) 
            else:
                ans += a[1] -rr
                heapq.heappush(l,-rr)
                heapq.heappush(l,-ll) 
                heapq.heappush(r,a[1])
                heapq.heappush(r,a[1]) 
        
    else:
        a = heapq.heappop(l)
        print(-a,ans)
        heapq.heappush(l,a)

Solution (Python):
import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign

q = int(input())
queries = [tuple(map(int, input().split())) for i in range(q)]
INF = 10 ** 12
small = Heapq([-INF],desc=True)
large = Heapq([INF])
fx_min = queries[0][2]
median = queries[0][1]
k = 0
for query in queries[1:]:
  if query[0] == 1:
    k += 1
    a,b = query[1],query[2]
    fx_min += abs(median-a) + b
    small_max, large_min = small.top(), large.top()
    if k % 2: 
      if (a <= median):
        small.push(a)
        large.push(median)
        median = small.top()
      else:
        small.push(median)
        large.push(a)
    else:
      if (a <= small_max):
        small.pop()
        small.push(a)
      elif (small_max < a <= large_min):
        fx_min -= abs(median-a)
        median = a
      else:
        large.push(a)
        newmed = large.pop()
        fx_min -= abs(median-newmed)
        median = newmed 
  else:
    print(median,fx_min)

Solution (Python):
import heapq
q=int(input())
L=[]
R=[]
heapq.heapify(L)
heapq.heapify(R)
fx=0
for i in range(q):
  Q=list(map(int,input().split()))
  if Q[0]==1:
    a,b=Q[1],Q[2]
    heapq.heappush(L,-a)
    heapq.heappush(R,a)
    l=-heapq.heappop(L)
    r=heapq.heappop(R)
    if l==a and r==a:
      heapq.heappush(L,-l)
      heapq.heappush(R,r)
    else:
      fx+=abs(r-l)
      heapq.heappush(L,-r)
      heapq.heappush(R,l)
    x=-L[0]
    fx+=b
  else:
    print(x,fx)

Solution (Python):
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
Q = int(input())
query = []
sumL, sumR = [], []
ans = 0
for _ in range(Q):
    a = list(map(int, input().split()))
    if a[0]==1:
        ans += a[2]
        if len(sumL)==0 or a[1] <= -sumL[0]:
            heappush(sumL, -a[1])
            ans += -sumL[0] - a[1]
        else:
            heappush(sumR, a[1])
            ans += sumL[0] + a[1]
    
        if len(sumR) > len(sumL):
            ans -= sumR[0] + sumL[0]
            heappush(sumL, -heappop(sumR))
            
        elif len(sumL) - len(sumR) >= 2:
            heappush(sumR, -heappop(sumL))

    else:
        print(-sumL[0],ans)

Solution (Python):

import heapq

n = int(input())

hq1 = []
hq2 = []
ans = 0

for _ in range(n):
    q = list(map(int, input().split()))
    if q[0]==1:
        heapq.heappush(hq1, q[1]*-1)
        heapq.heappush(hq2, q[1])
        hq1max = heapq.heappop(hq1)*-1
        hq2min = heapq.heappop(hq2)
        heapq.heappush(hq1, hq2min*-1)      
        heapq.heappush(hq2, hq1max)
        ans += abs(hq1max-hq2min) + q[2]        
    if q[0]==2:
        hq1max = heapq.heappop(hq1)*-1
        heapq.heappush(hq1, hq1max*-1)          
        print(hq1max, ans)

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

    Q = int(input())

    left = []
    right = []
    sum_l = 0
    sum_r = 0
    cnt = 0
    b = 0
    for _ in range(Q):
        query = map(int, input().split())
        t = next(query)
        if t == 1:
            x, b_ = query
            b += b_
            cnt += 1
            if cnt % 2 == 0:
                heappush(left, -x)
                sum_l += x
                x = -heappop(left)
                sum_l -= x
                heappush(right, x)
                sum_r += x
            else:
                heappush(right, x)
                sum_r += x
                x = heappop(right)
                sum_r -= x
                heappush(left, -x)
                sum_l += x
        else:
            x = -left[0]
            ans = b + sum_r - sum_l + x * (cnt % 2)
            print(x, ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input=sys.stdin.readline

Q=int(input())
ques=[[] for i in range(0,Q)]
value=set([])
for i in range(0,Q):
    ques[i]=list(map(int,input().split()))
    if ques[i][0]==1:
        value.add(ques[i][1])

value=list(value)
value.sort()
n=len(value)
dic={}
for i in range(n):
    dic[value[i]]=0
    dic[value[i]]=i


def segfunc(x,y):
    return x+y

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele =0


num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

index=dic[ques[0][1]]
update(index,1)
minx=ques[0][1]
minf=0
B=ques[0][2]
count=1
for i in range(1,Q):
    if ques[i][0]==2:
        print(minx,minf+B)
    else:
        a=ques[i][1]
        b=ques[i][2]
        index=dic[a]
        count+=1
        B+=b
        minf+=abs(a-minx)
        update(index,seg[index+num-1]+1)
        start=0
        end=n-1
        while end-start>1:
            test=(end+start)//2
            if query(0,test+1)>=(count+1)//2:
                end=test
            else:
                start=test

        if query(0,start+1)>=(count+1)//2:
            t=start
        else:
            t=end

        if value[t]>minx:
            if count%2==1:
                minf-=value[t]-minx
                minx=value[t]
            else:
                minf-=2*(value[t]-minx)
                minx=value[t]
        elif minx>value[t]:
            if count%2==1:
                minf-=value[t]-minx
                minx=value[t]
            else:
                minx=value[t]

Solution (Python):
q = int(input())
ans = [0, 0]
import heapq
p1 = []
p2 = []
heapq.heapify(p1)
heapq.heapify(p2)
sum_b = 0
sum_p1 = 0
sum_p2 = 0
for _ in range(q):
    ql = list(map(int,input().split()))
    if ql[0] == 2:
        if len(p1) == len(p2):
            print(-p2[0], sum_p1 - len(p1) * -p2[0] + len(p2) * -p2[0] - sum_p2 + sum_b)
        else:
            print(p1[0], sum_p1 - len(p1) * p1[0] + len(p2) * p1[0] - sum_p2 + sum_b)
    else:
        sum_b += ql[2]
        if len(p1) == 0:
            heapq.heappush(p1, ql[1])
            sum_p1 += ql[1]
        elif p1[0] <= ql[1]:
            heapq.heappush(p1, ql[1])
            sum_p1 += ql[1]
        else:
            heapq.heappush(p2, -ql[1])
            sum_p2 += ql[1]
        if len(p1) < len(p2):
            k = heapq.heappop(p2)
            heapq.heappush(p1, -k)
            sum_p2 += k
            sum_p1 -= k
        if len(p1) - 1 > len(p2):
            k = heapq.heappop(p1)
            heapq.heappush(p2, -k)
            sum_p1 -= k
            sum_p2 += k

Solution (Python):
Q = int(input())
qs = [input().split() for i in range(Q)]

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

    def size(self):
        return len(self.hq)

lq = Heapq([], True)
rq = Heapq([], False)

ofs = 0
for q in qs:
    if q[0] == '2':
        print(lq.top(), ofs)
        continue
    _,a,b, = q
    a,b = int(a),int(b)
    ofs += b
    lq.push(a)
    rq.push(a)
    if lq.top() > rq.top():
        l,r = lq.pop(), rq.pop()
        ofs += abs(l-r)
        lq.push(r)
        rq.push(l)

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(-1,0),(0,1),(0,-1)]

def main():
    sa = sb = 0
    hp1 = []
    hp2 = []
    m = None
    for _ in range(II()):
        ab=input().split()
        if ab[0]=="1":
            a,b=int(ab[1]),int(ab[2])
            sb+=b
            heappush(hp1,-a)
            heappush(hp2,a)
            while -hp1[0]>hp2[0]:
                heappush(hp1,-heappop(hp2))
                heappush(hp2,-heappop(hp1))
            if m==None:
                m=a
                continue
            if -hp1[0]>m:
                d=-hp1[0]-m
                sa+=(len(hp1)-1)//2*d-(len(hp2)+1)//2*d
            if -hp1[0]<m:
                d=hp1[0]+m
                sa+=-(len(hp1))//2*d+(len(hp2))//2*d
            sa += abs(m - a)
            m=-hp1[0]
        else:
            print(m,sa+sb)

main()

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

Q = int(input())
small = []
large = []
const = 0
total = 0
s = 0
n = 0
m = 0
for _ in range(Q):
    q, *nums = map(int, input().split())
    if q == 1:
        n += 1
        a, b = nums
        total += a
        const += b
        if n % 2 == 0:
            if a > large[0]:
                a = heappushpop(large, a)
            heappush(small, -a)
            m = -small[0]
            s += a
        else:
            if small and a < -small[0]:
                s += a
                a = -heappushpop(small, -a)
                s -= a
            heappush(large, a)
            m = large[0]
    else:
        ans = const + total - 2*s
        if n % 2 == 1:
            ans -= m
        print(m, ans)

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

Q = int(input())
querys = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
PQL, PQR = [], []
sumL = sumR = 0
numL = numR = 0
sumB = 0
for query in querys:
    if query[0] == 1:  
        a, b = query[1:]
        sumB += b
        if numL == 0:
            heappush(PQL, -a)
            sumL += a
            numL += 1
        elif numL == numR:
            if a <= -PQL[0]:
                heappush(PQL, -a)
                sumL += a
                numL += 1
            else:
                heappush(PQR, a)
                c = heappop(PQR)
                sumR += a-c
                heappush(PQL, -c)
                sumL += c
                numL += 1
        else:
            if a < -PQL[0]:
                heappush(PQL, -a)
                c = -heappop(PQL)
                sumL += a-c
                heappush(PQR, c)
                sumR += c
                numR += 1
            else:
                heappush(PQR, a)
                sumR += a
                numR += 1

    else:  
        x = -PQL[0]
        fx = numL*x - sumL + sumR - numR*x + sumB
        anss.append((x, fx))

print('\n'.join(map(lambda x: str(x[0])+' '+str(x[1]), anss)))

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

def main():
  less = []
  greater = []
  s = 0
  sum_ = 0
  q = int(input())
  def query(n):
    nonlocal s, sum_
    if n[0] == "1":
      c, a, b = map(int, n.split())
      s += b
      if len(less) == len(greater):
        if not greater or a <= greater[0]:
          heapq.heappush(less, -a)
          sum_ -= a
        else:
          r = heapq.heappushpop(greater, a)
          heapq.heappush(less, -r)
          sum_ += a - 2*r
      else:
        if a >= -less[0]:
          heapq.heappush(greater, a)
          sum_ += a
        else:
          r = -heapq.heappushpop(less, -a)
          heapq.heappush(greater, r)
          sum_ += 2*r - a
    else:
      res = sum_
      if len(less) > len(greater):
        res -= less[0]
      res += s
      print(-less[0], res)

  for _ in range(q):
    k = input()
    query(k)
    
if __name__ == "__main__":
  main()

Solution (Python):
"""
言い換えると次のことをすればよい
初期値をl = [], s = 0 として
'1 a b': lにaを追加、sにbを足す
'2': 中央値のインデックスより大きい要素の和-～～より小さい要素の和+sを出力
(要素が仮に昇順にソートされているなら、要素数をkとして、
sum(l[(k+1)//2:]) - sum(l[:k//2]) + s　を出力、xとしてはl[(k-1)//2]を出力
"""
import heapq

less = []
greater = []
s = 0
sum_ = 0
q = int(input())
def query(n):
  global s, sum_
  if n[0] == "1":
    c, a, b = map(int, n.split())
    s += b
    if len(less) == len(greater):
      if not greater or a <= greater[0]:
        heapq.heappush(less, -a)
        sum_ -= a
      else:
        r = heapq.heappushpop(greater, a)
        heapq.heappush(less, -r)
        sum_ += a - 2*r
    else:
      if a >= -less[0]:
        heapq.heappush(greater, a)
        sum_ += a
      else:
        r = -heapq.heappushpop(less, -a)
        heapq.heappush(greater, r)
        sum_ += 2*r - a
  else:
    res = sum_
    if len(less) > len(greater):
      res -= less[0]
    res += s
    print(-less[0], res)
    
for _ in range(q):
  k = input()
  query(k)