1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int szczupak(map<unsigned long long,unsigned long long> &m, unsigned long long s, unsigned long long k)
{
	int r=0;
	map<unsigned long long,unsigned long long> tmp;
	while(s<k && !m.empty() && m.begin()->first<s)
	{
		auto it = m.lower_bound(s);
		//printf("%llu %llu %d\n",s,it->first,it==m.end());
		unsigned long long cel = it == m.end()?k:it->first+1;
		cel = cel>k?k:cel;
		it--;
		

		unsigned long long ile = (cel-s-1) / (it->first)+1;
		ile = ile > it->second ? it->second : ile;
		//printf("cel:%llu s:%llu cel-s:%llu first:%llu ile:%llu\n",cel,s,cel-s,it->first,ile);

		s+=it->first * ile;
		it->second-=ile;
		tmp[it->first]+=ile;
		if(it->second==0)m.erase(it);
		r+=ile;
/*
		it--;
		s+=it->first;
		it->second--;
		if(it->second==0)m.erase(it);
		r++;
*/
	}
	for(auto it = tmp.begin();it!=tmp.end();it++)
	{
		m[it->first]+=it->second;
	}
	if(s>=k)return r;
	else return -1;
}

int main() {
	// your code goes here
	unsigned long long n;
	unsigned long long w,sum=0;
	scanf("%llu",&n);
	map<unsigned long long,unsigned long long>m;
	for(unsigned long long i =0;i<n;i++)
	{
		scanf("%llu",&w);
		m[w]++;
		sum+=w;
	}
	unsigned long long q;
	scanf("%llu",&q);
	for(unsigned long long i=0;i<q;i++)
	{
		int c;
		scanf("%d",&c);
		switch(c)
		{
			case 1:
				unsigned long long s,k;
				scanf("%llu%llu",&s,&k);
				if(k<=s)printf("0\n");
				else if(k-s>sum) printf("-1\n");
				else printf("%d\n",szczupak(m,s,k));
			break;
			case 2:
				scanf("%llu",&w);
				m[w]++;
				sum+=w;
			break;
			case 3:
				scanf("%llu",&w);
				m[w]--;
				if(m[w]==0)m.erase(w);
				sum-=w;
			break;
		}
	}
	
	return 0;
}