#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	multiset<int> s;
	cin>>n>>q;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		s.insert(x);
	}
	while(q--){
		int op;
		cin>>op;
		if(op==0){
			int x;
			cin>>x;
			s.insert(x);
		}
		else if(op==1){
			auto it=s.begin();
			cout<<*it<<'\n';
			s.erase(it);
		}
		else{
			auto it=s.end();
			it--;
			cout<<*it<<'\n';
			s.erase(it);
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, q;cin >> n >> q;
    vector<int> a(n);
    
    for (auto &x : a)cin >> x;
    multiset<int> s(a.begin(), a.end());

    while (q--)
    {
        int op;cin >> op;
        if (op == 0)
        {
            int x;
            cin >> x;
            s.insert(x);
        }
        else if (op == 1)
        {
            auto it = s.begin();
            cout << *it << '\n';
            s.erase(it);
        }
        else
        {
            auto it = s.end();
            it--;
            cout << *it << '\n';
            s.erase(it);
        }
    }
    return 0;
}