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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>  
using namespace std;

int main() {
	int n, k, q;
	long long int a;
	long long int begin_size, end_size, size;

	unordered_set<int> used;
	multiset<pair<long long int, int> > v;

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &a);
		int r = rand()*rand();
		v.insert(make_pair(a, r));
	}

	//sort(v.begin(), v.end());

	scanf("%d", &k);
	for (int i = 0; i < k; i++)
	{
		scanf("%d", &q);

		if (q == 1) //szczupak
		{
			used.clear();

			int result = 0;
			scanf("%lld%lld", &begin_size, &end_size);

			if (begin_size >= end_size)
			{
				printf("0\n");
				continue;
			}

			long long int size = begin_size;

			int j = 0;

			while (true)
			{
				//printf("size1: %lld\n",size);
				
				set<pair<long long int, int> >::iterator it;
				it = v.lower_bound(make_pair(size, 0));

				if (it == v.begin())
				{
					printf("-1\n");
					break;
				}
				it--;

				while (it != v.begin() && used.find(it->second) != used.end())
					it--;

				if (it == v.begin() && (used.find(it->second) != used.end() || it->first >= size))
				{
					printf("-1\n");
					break;
				}
				else
				{
					size += it->first;
					pair<long long int, bool> z = make_pair(it->first, true);
					used.insert(it->second);
					result++;

					if (size >= end_size)
					{
						printf("%d\n", result);
						break;
					}
				}
			}

		}

		if (q == 2) //dodanie szprotki
		{
			scanf("%lld", &size);
			int r = rand()*rand();
			v.insert(make_pair(size,r));
		}

		if (q == 3) //usuniecie szprotki
		{
			scanf("%lld", &size);
			v.erase(v.lower_bound(make_pair(size, -1000 * 1000 * 1000)));
		}

		//for (int i = 0; i < v.size(); i++)
		//	printf("%d ",v[i]);
		//printf("\n");	

	}

}