trait MyQueue[T] {
  def insert(x:T):Unit
  def check:Boolean
  def top: T
  def pop: Unit
}

import scala.collection.mutable._

class Queue[T<:Comparable[T]]( val L: Array[T]) extends MyQueue[T]{
  var size:Int = 0
  def top():T={
    if(size == 0) throw new Exception("Pusty kopiec")
    else
     L(0)
  }
  
  def swap(pos1:Int, pos2:Int){
    var temp:T = L(pos1)
    L(pos1) = L(pos2)
    L(pos2) = temp
  }
  
  def insert(x:T)={
     if(size == 101) throw new Exception("Pelny kopiec")
     if(size == 0){
       L(0) = x //= new Element(x,p)
       size = size + 1
     }
     else {
       L(size) = x
       var pos = size
       size = size + 1
       while(x.compareTo(L((pos-1)/2)) > 0){
         swap(pos, (pos-1)/2)
         pos = pos/2
       }     
     }     
  }
  
  def pop()={
      if(size == 0) throw new Exception("Pusty kopiec")
      else{
        var pos:Int = 0
        size = size - 1
        swap(pos,size)
        
        
        if(size != 0)
        while(pos*2+1<size && pos*2+2>= size &&(L(pos).compareTo(L(pos * 2 + 1)) < 0) || pos*2+2<size &&((L(pos).compareTo(L(pos * 2 + 1)) < 0) || (L(pos).compareTo(L(pos * 2 + 1)) < 0))){
          if(pos*2+1 < size && pos*2+2>= size)
            swap(pos,pos*2+1)
            else{
              if(L(pos * 2 + 1).compareTo(L(pos * 2 + 2)) > 0){
                swap(pos, pos * 2 + 1)
                pos = pos * 2 + 1
              }
              else{
                swap(pos, pos * 2 + 2)
                pos = pos * 2 + 2
              }
            }
      }
        
      }
  }
  def check()={
    size == 0
  }
}