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
#include <iostream>
#include <vector>

using namespace std;

int main() {
	long n;

	cin >> n;

	const int maxNBits = 20;// max value of n can be 10^6; it has 20 bits
	const int maxA = 201718;

	vector<int> capitalBits(maxNBits+maxA,0);

	long b = 0;

	for (long i = 0; i < n; ++i) {
		long a;

		cin >> a;

		long carryIndex=a;

		while (capitalBits[carryIndex]==1)
		{
			capitalBits[carryIndex] = 0;
			++carryIndex;
		}
		capitalBits[carryIndex] = 1;
		
		if (carryIndex > b) {
			b = carryIndex;
		}
	}

	cout << b << endl;

	return 0;
}