struct myPair{
    long long dis;
    int pos;
    myPair(int d = 0,int p = 1):dis(d),pos(p){}
    bool operator<(const myPair& x){
        return x.dis < dis;
    }
};
struct Heap{
    int size_;
    int cap;
    myPair* arr;
    Heap(int n){
        size_ = 0;
        cap = N;
        arr = new myPair[N + 1];
    }
    ~Heap (){}
    void push(myPair val){
    if( size_ >= cap) {
        myPair* temp = new myPair [cap << 1];
        for(int i = 1; i <= cap; i++) {
            temp[i] = arr[i];
        }
        arr=temp;
        cap<<=1;
    }
    size_ ++;
    arr[size_] = val;
    up(size_);
    }

    myPair pop(){
        myPair ans = arr[1];
        std::swap(arr[1],arr[size_--]);
        down(1);
        return ans;
    }
    void up(int n){
        while( n > 1 && arr[n] < arr[n>>1] ){//如果arr[n]比父亲节点的优先级大，将其上浮
        std::swap(arr[n],arr[n>>1]);
        n >>= 1;
    }

    }
    void down(int n ){
        while(n*2 <= size_){
        int k = 2*n;
        if(k < size_ && arr[k+1]<arr[k]) k++;//选出左右孩子中优先级更高的那个
        if(arr[k]<arr[n]){
            std::swap(arr[n],arr[k]);
            n = k;
        }
        else break;
    }
    }
    int size(){
        return size_;
    }
    bool empty(){
        return size_ == 0;
    }
    myPair top(){
        return arr[1];
    }
};