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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <cstdio>
#include <map>
#include <functional>
#include <chrono>
#include <iostream>
using namespace std;

typedef unsigned long long int ull;
map<unsigned long long int, int, greater<unsigned long long int> > fishes;

int attact(ull actual, ull desired) {
	
	int eaten = 0;
	map<ull, int>::iterator it;
	map<unsigned long long int, int> history;
	

	// printf("\n\nSTAN RYB\n");
// 	for(it = fishes.begin(); it!= fishes.end(); it++) {
// 		printf("(w:%llu -> c:%d) ", it->first, it->second);
// 	}
// 	printf("\n");
// printf("waze %llu, chcialbym %llu\n", actual, desired);
	
	while (actual < desired) {
		it = fishes.upper_bound(actual);
		// printf("najwieksze co moge zjesc wazy %llu %d\n", it -> first, it -> second);
		if (it -> second == 0) { // nie ma mniejszych ryb
			eaten = -1;		
			break;
		}
		// printf("jestem wiekszy to jem, dostepna ilosc %d\n", it -> second);
		ull weight = it -> first;
		int count = it -> second; 
		

		if (it == fishes.begin()) { // nie ma wiekszych ryb
			// printf("Jestem nawieksza ryba, jem ile potrzeba albo wszystko\n");
			ull dif = 1 + (desired - actual - 1) / weight;
			if (dif >= count) {
				// printf("Zjazdam wszyskie %d\n", count);
				actual += count * weight;
				fishes.erase(weight);
				eaten += count;
				history[weight] += count; 
			} else {
				// printf("Zjazdam ile potrzebuje do większej %llu\n", dif);
				actual += dif * weight;
				fishes[weight] -= dif;
				eaten += dif;
				history[weight] += dif;
			}
		} else {
			it--;
			// printf("nastepna ryba wazy %llu i jest dostepna w ilosci %d \n", it->first, it->second);
		
			ull next_weight = it -> first;
		
			// ile zjesc żeby moc zjesc wieksza?
			ull dif = 1 + (next_weight - actual) / weight;
			// printf("Musze zjesc %llu ryb (%llu), żeby moc zjesc wieszka (%llu)\n", dif, weight, next_weight);
			
			// ile ryb musze zjesc zeby osiagnac pozadany rozmiar?
			ull dif2 = 1 + (desired - actual - 1) / weight;
			if (dif2 <= dif) { // szybciej osiagne rozmiat ostateczny niz zeby jesc kolejna rybe
				// printf("Mozliwe, ze moge zjesc ta i osiagnać wystarczający rozmiar. jedzienie -> %llu koenic -> %llu\n", dif, dif2);
				dif = dif2;
 			}
			if (dif >= count) {
				// printf("Zjazdam wszyskie %d\n", count);
				actual += count * weight;
				fishes.erase(weight);
				eaten += count;
				history[weight] += count; 
			} else {
				// printf("Zjazdam ile potrzebuje do większej %llu\n", dif);
				actual += dif * weight;
				fishes[weight] -= dif;
				eaten += dif;
				history[weight] += dif; 
			}
			
		}
		// printf("waze %llu, chcialbym %llu, zjadłem %d ryb\n", actual, desired, eaten);
		// printf("\n\nSTAN RYB\n");
		// for(it = fishes.begin(); it!= fishes.end(); it++) {
		// 	printf("(w:%llu -> c:%d) ", it->first, it->second);
		// }
		// printf("\n");
		
	}
	
	// przywrócić stan jeziora
	for (it = history.begin(); it != history.end(); it++) {
		fishes[it->first] += it-> second;
	}

	return eaten;
}

int main() {
	int n, q, t;
	ull tmp, w, s, k;
	map<unsigned long long int, int>::iterator it;
	
	scanf("%d", &n);
	for(int i=0; i<n;i++) {
		scanf("%llu", &tmp);
		fishes[tmp]++;
	}

	// printf("=========================================================================\n");
	// 	printf("=========================================================================\n");
	// 		printf("=========================================================================\n");
	// for(it = fishes.begin(); it!= fishes.end(); it++) {
	// 	printf("(w:%llu -> c:%d) ", it->first, it->second);
	// }
	// printf("\n");
	
		// //
	// printf("lb1  %llu\n", fishes.upper_bound(1)->first);
	// printf("lb2  %llu\n", fishes.upper_bound(2)->first);
	// printf("lb3  %llu\n", fishes.upper_bound(3)->first);
	// printf("lb4  %llu\n", fishes.upper_bound(4)->first);
	// printf("lb7  %llu\n", fishes.upper_bound(7)->first);
	//  printf("lb8  %llu\n", fishes.upper_bound(8)->first);
	//  printf("lb10 %llu\n", fishes.upper_bound(10)->first);
	//	
	scanf("%d", &q);
	
	
	for(int i=0; i<q;i++) {
		scanf("%d", &t);
		if (t == 1) {
			scanf("%llu %llu", &s, &k);
			printf("%d\n", attact(s, k));
		} else {
			scanf("%llu", &w);
			if (t == 2) {
				fishes[w]++;
			} else {
				fishes[w]--;
				if (fishes[w] == 0) {
					fishes.erase(w);
				}
			}
		}
	}
	
	return 0;
}