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
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <stack>

using weight = int64_t;
using weights = std::multiset<int64_t>;
using weight_iter = weights::const_iterator;

struct Frame {
	const weight pike;
	const int eaten;
	const weight_iter start_at;

	Frame(weight pike, int eaten, weight_iter start_at) : pike(pike), eaten(eaten), start_at(start_at) {}
};

weight_iter next(const weight_iter iter) {
	weight_iter copy = weight_iter(iter);
	++copy;
	return copy;
}

int min_sprats_rec(weight pike, weight pike_target, int eaten, int min_eaten, const weights& sprats, weight_iter start_at) {
	if (pike >= pike_target) {
		return std::min(eaten, min_eaten);
	}
	for (weight_iter it = start_at; it != sprats.end(); it++) {
		weight sprat = *it;
		if (sprat < pike) {
			min_eaten = min_sprats_rec(pike + sprat, pike_target, eaten + 1, min_eaten, sprats, next(it));
		}
	}
	return min_eaten;
}

int min_sprats_iter(weight pike_start, weight pike_target, const weights& sprats) {
	int min_eaten = INT_MAX;

	std::stack<Frame> frames = std::stack<Frame>();
	frames.push(Frame(pike_start, 0, sprats.begin()));

	while (!frames.empty()) {
		Frame f = frames.top();
		frames.pop();

		if (f.pike >= pike_target) {
			min_eaten = std::min(f.eaten, min_eaten);
		}
		else {
			for (weight_iter it = f.start_at; it != sprats.end(); it++) {
				weight sprat = *it;
				if (sprat < f.pike) {
					frames.push(Frame(f.pike + sprat, f.eaten + 1, next(it)));
				}
			}
		}
	}
	return min_eaten;
}

int main() {
	int sprat_count;
	std::cin >> sprat_count;

	weights sprats = weights();
	for (int s = 0; s < sprat_count; s++) {
		weight sprat;
		std::cin >> sprat;
		sprats.insert(sprat);
	}

	int event_count;
	std::cin >> event_count;

	for (int e = 0; e < event_count; e++) {
		int event;
		std::cin >> event;

		if (event == 1) {
			weight pike, pike_target;
			std::cin >> pike >> pike_target;
			int eaten = min_sprats_iter(pike, pike_target, sprats);
			std::cout << (eaten == INT_MAX? -1 : eaten) << std::endl;
		}
		else if (event == 2) {
			weight sprat;
			std::cin >> sprat;
			sprats.insert(sprat);
		}
		else if (event == 3) {
			weight sprat;
			std::cin >> sprat;
			sprats.erase(sprats.lower_bound(sprat));
		}
	}
	return 0;
}