Sol

阅读题意可知，这题我们需要动态维护序列的最大值最小值。

每次操作进行修改最大最小并重排的复杂度是错误的，达到了 $\mathcal O(q\times n \log n)$ 的级别。

那么，我们不难想到 C++ 的 STL，multiset。

multiset 与 set 的区别在与，multiset 的元素是可以重复的。根据题意及样例，这里可能会有重复元素出现。

下面介绍一下 multiset：

1. multiset 位于 set 库中。请使用 #include<set> 等或使用包含 set 库的库。
2. multiset<type>mst 建立一个 type 类型的 multiset 容器。type 可以是 int/long long/pair<int,int>/string 等。
3. mst.clear() 清空。
4. mst.insert(x) 向集合插入元素 $x$。
5. mst.empty() 查询集合是否为空。
6. mst.begin()/mst.end() 返回集合开头/结尾迭代器。代码中所用的 *s.begin() 和 *(--s.end()) 即为开头与结尾元素。
7. mst.erase(x) 删除迭代器为 $x$ 的元素。

乱搞做法：平衡树。

赛时码不出来怎么办？C++ 拥有强大的 pb_ds 库，可以直接实现。但是在提交的时候请选择开启 O2 优化的语言，因为 pb_ds 在无 O2 下的表现极劣。

Code

/*
Auther:  zjs123
Luogu:   754000
QQ:      755328053
*/
#include<bits/stdc++.h>
using namespace std;
int n,t;
int op;
long long x,a,b;
multiset<long long> s;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a;
		s.insert(a);
	}
	cin>>t;
	while(t--){
		cin>>op>>b;
		if(op==1)x=b;
		else if(op==2){
			s.erase(--s.end());
			s.insert(b);
		}
		else{
			s.erase(s.begin());
			s.insert(b);
		}
		cout<<*(--s.end())+x<<"\n";
	}
	return 0;
}