module mod_priority_queue
  implicit none
  type t_priority_queue
    private
    integer :: num = 0 !中に入ってる物の数
    integer, pointer :: heap(:) => null()!pqの容量
  contains
    procedure :: offer => offer
    procedure :: clear => clear
    procedure :: poll => poll
    procedure :: peek => peek
    procedure :: size => size_of
  end type t_priority_queue
contains
  subroutine offer(pq,item)
    class(t_priority_queue), intent(inout) :: pq
    integer, intent(in) :: item
    integer :: n, i, t
    integer, allocatable :: tmp(:)
    if (.not.associated(pq%heap)) allocate(pq%heap(1))

    !いっぱいいっぱいのときには拡張している
    if (pq%num == size(pq%heap)) then
      allocate(tmp(pq%num))
      tmp = pq%heap
      deallocate(pq%heap)
      allocate(pq%heap(2*pq%num))
      pq%heap(1:pq%num) = tmp
      deallocate(tmp)
    end if

    pq%num = pq%num+1
    pq%heap(pq%num) = item
    n = pq%num
    do while (n > 1)
      i = n/2
      if (pq%heap(n) > pq%heap(i)) then
        t = pq%heap(n)
        pq%heap(n) = pq%heap(i)
        pq%heap(i) = t
      end if
      n = i
    end do
    return
  end subroutine offer

  subroutine clear(pq)
    class(t_priority_queue), intent(inout) :: pq
    if (associated(pq%heap)) deallocate(pq%heap)
    pq%num = 0
    return
  end subroutine clear

  function poll(pq) result(item)
    class(t_priority_queue), intent(inout) :: pq
    integer :: item, n, i, j, tmp
    n = pq%num
    item = pq%heap(1)
    pq%heap(1) = pq%heap(n)
    pq%num = pq%num-1
    i = 1
    do while (2*i < n)
      j = 2*i
      if (j+1 < n .and. pq%heap(j+1) > pq%heap(j)) j = j+1
      if (pq%heap(j) > pq%heap(i)) then
        tmp = pq%heap(j)
        pq%heap(j) = pq%heap(i)
        pq%heap(i) = tmp
      end if
      i = j
    end do
  end function poll
  subroutine pop(pq)
    class(t_priority_queue), intent(inout) :: pq
    integer :: item, n, i, j, tmp
    n = pq%num
    item = pq%heap(1)
    pq%heap(1) = pq%heap(n)
    pq%num = pq%num-1
    i = 1
    do while (2*i < n)
      j = 2*i
      if (j+1 < n .and. pq%heap(j+1) > pq%heap(j)) j = j+1
      if (pq%heap(j) > pq%heap(i)) then
        tmp = pq%heap(j)
        pq%heap(j) = pq%heap(i)
        pq%heap(i) = tmp
      end if
      i = j
    end do
  end subroutine 
    
  function peek(pq) result(item)
    class(t_priority_queue), intent(inout) :: pq
    integer :: item
    item = pq%heap(1)
  end function peek

  integer function size_of(pq)
    class(t_priority_queue), intent(in) :: pq
    size_of = pq%num
  end
end module mod_priority_queue

program am
use mod_priority_queue
implicit none
integer::Q
integer::T,A(2)
integer(16)::ANS

type(t_priority_queue)::L,R
integer::i

read*,Q
ANS=0
call offer(L,-huge(i))
call offer(R,-huge(i))
do i=1,Q
    read*,T,A(2*T-1:2)
    select case(T)
    case(1)
        ANS=ANS+A(2)
        if(A(1)<peek(L))then
            ANS=ANS+peek(L)-A(1)
        else if(-peek(R)<A(1))then
            ANS=ANS+A(1)+peek(R)
        endif
        call offer(l,A(1))
        call offer(r,-A(1))
        if(peek(L)>-peek(R))then
            call offer(l,-peek(R))
            call offer(r,-peek(l))
            call pop(l)
            call pop(r)
        endif
    case(2)
        print"(i0,a,i0)",peek(l)," ",ANS
    end select
end do
end program am