module mod_tree_map
  implicit none
  type t_entry
    private
    integer :: key
    integer :: val
  end type
  type t_node
    private
    type(t_node), pointer :: left => null(), right => null()
    integer :: level = 1
    type(t_entry), pointer :: e => null()
  end type
  type t_tree_map
    private
    type(t_node), pointer :: root => null()
    integer :: deflt = -1
  contains
    procedure :: size => size_of
    procedure :: clear => clear
    procedure :: set_default => set_default
    procedure :: put => put
    procedure :: remove => remove
    procedure :: get => get
    procedure :: contain => contain
    procedure :: first_key => get_first_key
    procedure :: last_key => get_last_key
    procedure :: floor_key => floor_key
    procedure :: lower_key => lower_key
    procedure :: ceiling_key => ceiling_key
    procedure :: higher_key => higher_key
    procedure :: get_keys => get_keys
  end type
contains
  function new_entry(key,val) result(e)
    integer, intent(in) :: key
    integer, intent(in) :: val
    type(t_entry), pointer :: e
    e => null()
    allocate(e)
    e%key = key
    e%val = val
  end
  function new_node(e) result(n)
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    n => null()
    allocate(n)
    n%e => e
  end
  integer function level(n)
    type(t_node), pointer, intent(in) :: n
    level = 0
    if (.not.associated(n)) return
    level = n%level
  end
  logical function is_leaf(n)
    type(t_node), pointer, intent(in) :: n
    is_leaf = associated(n) .and. .not.associated(n%left) .and. &
    &         .not.associated(n%right)
  end
  recursive function tree_size(n) result(s)
    type(t_node), pointer, intent(in) :: n
    integer :: s
    s = 0
    if (.not.associated(n)) return
    s = 1+tree_size(n%left)+tree_size(n%right)
  end
  function skew(n) result(l)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: l
    l => n
    if (.not.(associated(n) .and. associated(n%left) .and. &
    &   n%left%level == n%level)) return
    l => n%left
    n%left => l%right
    l%right => n
  end
  function split(n) result(r)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: r
    r => n
    if (.not.(associated(n) .and. associated(n%right) .and. &
    &   associated(n%right%right) .and. n%right%right%level == n%level)) return
    r => n%right
    n%right => r%left
    r%left => n
    r%level = r%level+1
  end
  function predecessor(n) result(p)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: p
    p => null()
    if (.not.associated(n%left)) return
    p => n%left
    do while (associated(p%right))
      p => p%right
    end do
  end
  function successor(n) result(s)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: s
    s => null()
    if (.not.associated(n%right)) return
    s => n%right
    do while (associated(s%left))
      s => s%left
    end do
  end
  recursive function insert(n,e) result(t)
    type(t_node), pointer, intent(in) :: n
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: t
    t => new_node(e)
    if (.not.associated(n)) return
    t => n
    if (e%key < t%e%key) then
      t%left => insert(t%left,e)
    else if (e%key > t%e%key) then
      t%right => insert(t%right,e)
    else
      t%e => e
    end if
    t => skew(t)
    t => split(t)
  end
  recursive function delete(n,e) result(t)
    type(t_node), pointer, intent(in) :: n
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: t, l
    t => n
    if (.not.associated(n)) return
    if (e%key < t%e%key) then
      t%left => delete(t%left,e)
    else if (e%key > t%e%key) then
      t%right => delete(t%right,e)
    else
      if (is_leaf(t)) then
        t => null()
        return
      end if
      if (.not.associated(t%left)) then
        l => successor(t)
        t%right => delete(t%right,l%e)
        t%e => l%e
      else
        l => predecessor(t)
        t%left => delete(t%left,l%e)
        t%e => l%e
      end if
    end if
    t => decrease_level(t)
    t => skew(t)
    t%right => skew(t%right)
    if (associated(t%right)) t%right%right => skew(t%right%right)
    t => split(t)
    t%right => split(t%right)
  end
  function decrease_level(n) result(t)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: t
    integer :: should_be
    t => n
    should_be = min(level(t%left),level(t%right))+1
    if (t%level > should_be) then
      t%level = should_be
      if (level(t%right) > should_be) t%right%level = should_be
    end if
  end
  recursive subroutine release_tree(t)
    type(t_node), pointer, intent(inout) :: t
    if (.not.associated(t)) return
    call release_tree(t%left)
    call release_tree(t%right)
    deallocate(t)
  end
  recursive subroutine get_keys_list(t,keys,num)
    type(t_node), pointer, intent(in) :: t
    integer, intent(inout) :: keys(:)
    integer, intent(inout) :: num
    if (.not.associated(t)) return
    call get_keys_list(t%left,keys,num)
    num = num+1
    keys(num) = t%e%key
    call get_keys_list(t%right,keys,num)
  end
  integer function size_of(this)
    class(t_tree_map), intent(in) :: this
    size_of = tree_size(this%root)
  end
  subroutine clear(this)
    class(t_tree_map), intent(inout) :: this
    call release_tree(this%root)
    this%root => null()
  end
  subroutine set_default(this,deflt)
    class(t_tree_map), intent(inout) :: this
    integer, intent(in) :: deflt
    this%deflt = deflt
  end
  subroutine put_entry(this,e)
    type(t_tree_map), intent(inout) :: this
    type(t_entry), pointer, intent(in) :: e
    this%root => insert(this%root,e)
  end
  subroutine remove_entry(this,e)
    type(t_tree_map), intent(inout) :: this
    type(t_entry), pointer, intent(in) :: e
    this%root => delete(this%root,e)
  end
  function get_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        n => n%left
      else if (e%key > n%e%key) then
        n => n%right
      else
        ret => n%e
        return
      end if
    end do
  end
  function contain_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    logical :: ret
    ret = .false.
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        n => n%left
      else if (e%key > n%e%key) then
        n => n%right
      else
        ret = .true.
        return
      end if
    end do
  end
  function get_first_entry(this) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%left))
      n => n%left
    end do
    ret => n%e
  end
  function poll_first_entry(this) result(ret)
    type(t_tree_map), intent(inout) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%left))
      n => n%left
    end do
    ret => n%e
    this%root => delete(this%root,ret)
  end
  function get_last_entry(this) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%right))
      n => n%right
    end do
    ret => n%e
  end
  function poll_last_entry(this) result(ret)
    type(t_tree_map), intent(inout) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%right))
      n => n%right
    end do
    ret => n%e
    this%root => delete(this%root,ret)
  end
  function floor_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        n => n%left
      else if (e%key > n%e%key) then
        if (.not.associated(ret)) then
          ret => n%e
          cycle
        end if
        if (e%key-ret%key > e%key-n%e%key) ret => n%e
        n => n%right
      else
        ret => n%e
        return
      end if
    end do
  end
  function lower_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_entry), pointer :: ret
    ret => floor_entry(this,new_entry(e%key-1,0))
  end
  function ceiling_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        if (.not.associated(ret)) then
          ret => n%e
          cycle
        end if
        if (e%key-ret%key < e%key-n%e%key) ret => n%e
        n => n%left
      else if (e%key > n%e%key) then
        n => n%right
      else
        ret => n%e
        return
      end if
    end do
  end
  function higher_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_entry), pointer :: ret
    ret => ceiling_entry(this,new_entry(e%key+1,0))
  end
  subroutine get_keys(this,keys,num)
    class(t_tree_map), intent(in) :: this
    integer, intent(inout) :: keys(:)
    integer, intent(inout) :: num
    keys = 0
    num = 0
    call get_keys_list(this%root,keys,num)
  end
  subroutine put(this,key,val)
    class(t_tree_map), intent(inout) :: this
    integer, intent(in) :: key
    integer, intent(in) :: val
    call put_entry(this,new_entry(key,val))
  end
  subroutine remove(this,key)
    class(t_tree_map), intent(inout) :: this
    integer, intent(in) :: key
    call remove_entry(this,new_entry(key,0))
  end
  function get(this,key) result(val)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: val
    val = this%deflt
    tmp => get_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    val = tmp%val
  end
  logical function contain(this,key)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    contain = contain_entry(this,new_entry(key,0))
  end
  function get_first_key(this) result(key)
    class(t_tree_map), intent(in) :: this
    type(t_entry), pointer :: tmp
    integer :: key
    key = this%deflt
    tmp => get_first_entry(this)
    if (.not.associated(tmp)) return
    key = tmp%key
  end
  function get_last_key(this) result(key)
    class(t_tree_map), intent(in) :: this
    type(t_entry), pointer :: tmp
    integer :: key
    key = this%deflt
    tmp => get_last_entry(this)
    if (.not.associated(tmp)) return
    key = tmp%key
  end
  function floor_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => floor_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
  function lower_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => lower_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
  function ceiling_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => ceiling_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
  function higher_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => higher_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
end module mod_tree_map
program powers_of_two
  use mod_tree_map
  implicit none
  type(t_tree_map) :: map
  integer :: n, i, j = 1, m = 0, x, y, p, k = 0
  integer, dimension(200001) :: a = 0, b = 0, c = 0
  read(*,*) n
  read(*,*) a(1:n)
  call quick_sort(a(1:n))
  i = 1
  do while (i <= n)
    do while (a(j) == a(i))
      j = j+1
    end do
    k = k+1
    b(k) = a(i)
    c(k) = j-i
    call map%put(a(i),k)
    i = j
  end do
  do while (k > 0)
    x = b(k)
    call map%remove(x)
    p = c(k)
    c(k) = 0
    k = k-1
    if (p == 0) cycle
    y = 2*highest_one_bit(x)-x
    if (x < y) cycle
    if (x == y) then
      m = m+p/2
      cycle
    end if
    i = map%get(y)
    if (i < 0) cycle
    m = m+min(p,c(i))
    c(i) = max(c(i)-p,0)
    if (c(i) == 0) call map%remove(y)
  end do
  write(*,'(i0)') m
contains
  function highest_one_bit(i) result(ret)
    integer, intent(in) :: i
    integer :: ret
    ret = i
    ret = or(ret,rshift(ret,1))
    ret = or(ret,rshift(ret,2))
    ret = or(ret,rshift(ret,4))
    ret = or(ret,rshift(ret,8))
    ret = or(ret,rshift(ret,16))
    ret = ret-rshift(ret,1)
  end
  recursive subroutine quick_sort(a)
    integer, intent(inout) :: a(:)
    integer :: n, l, r, m
    integer :: p
    n = size(a)
    l = 1
    r = n
    m = (n+1)/2
    p = a(l)+a(m)+a(r)-max(a(l),a(m),a(r))-min(a(l),a(m),a(r))
    do
      do while (a(l) < p)
        l = l+1
      end do
      do while (a(r) > p)
        r = r-1
      end do
      if (l >= r) exit
      a(l) = xor(a(l),a(r))
      a(r) = xor(a(l),a(r))
      a(l) = xor(a(l),a(r))
      l = l+1
      r = r-1
    end do
    if (l-1 > 1) call quick_sort(a(1:l-1))
    if (n > r+1) call quick_sort(a(r+1:n))
  end
end program powers_of_two

Measured memory_bytes: 249984