//字典树

//变量
int son[N][26], cnt[N], idx;
//操作
//插入
void insert(char str[]){
    int p = 0;
    for(int i = 0; str[i]; ++ i){
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
//查询
void query(char str[]){
    int p = 0;
    for(int i = 0; str[i]; ++ i){
        int u = str[i] - 'a';
        if(!son[p][u]) return ;
        p = son[p][u];
    }
    return cnt[p];
}

//朴素并查集

//变量
int f[N];
//操作
//初始化
void init(){
    for(int i = 1; i <= n; ++ i) f[i] = i;
}
//查询
int find(int x){
    return x == f[x] ? x : (f[x] = find(f[x]));
}
//合并
void merge(int u, int v){
    f[find(u)] = f[find(v)];
}

//维护size的并查集
//变量
int f[N], size[N];
//操作
//初始化
void init(){
    for(int i = 1; i <= n; ++ i){
        f[i] = i;
        size[i] = 1;
    }
}
//查询
void query(int x){
    return x == f[x] ? x : (f[x] = find(f[x]));
}
//合并
void merge(int u, int v){
    size[find(u)] += size[find(v)];
    f[find(v)] = f[find(u)];
}

//小根堆

//变量
int h[N], idx;
//操作
//down函数
void down(int u){
    int t = u, l = 2 * u, r = 2 * u + 1;
    if(l <= idx && h[l] < h[t]) t = l;
    if(r <= idx && h[r] < h[t]) t = r;
    if(t != u)swap(h[t] , h[u]), down(t);
}
//up函数
void up(int u){
    while(u / 2 && h[u] < h[u / 2]){
        swap(h[u], h[u / 2]);
        u >>= 1;
    }
}
//初始化
void init(){
    //存储
    int x;
    for(int i = 1; i <= n; ++ i){
        cin >> x;
        h[ ++ idx] = x
    }
   //建堆
   for(int i = n / 2; i; -- i) down(i);
}
//插入x
void add(int x){
    h[ ++ idx] = x;
    up(idx);
}
//删除k
void del(int k){
    h[k] = h[idx];
    idx -- ;
    up(k); down(k);
}
//改
void change(int k, int x){
    h[k] = x;
    up(k); down(k);
}

//高级操作
//变量
int h[N], ph[N], hp[N], idx, k;
//操作
//交换
void swap_head(int u, int v){
    swap(h[u], h[v]);
    swap(hp[u], hp[v]);
    swap(ph[hp[u]], ph[hp[v]]);
}
//up,down中的swap()全部换为swap_head()
//初始化
void init(){
    //存储
    int x;
    for(int i = 1; i <= n; ++ i){
        cin >> x;
        idx ++ ; k ++ ;
        h[idx] = x;
        //hp[idx] = m;
        //ph[m] = idx;
    }
    //建堆
    for(int i = n / 2; i; -- i) down(i);
}
//add
void add(int x){
    ++ idx; ++ k;
    h[idx] = x;
    ph[k] = idx;
    hp[idx] = k;
    up(idx);
}