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
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>

typedef long long lLong;
typedef unsigned long uLong;
typedef unsigned long long ulLong;
typedef unsigned int uInt;
typedef unsigned char Byte;

using namespace std;

#define FOR(x, b, e) for(int x=b; x<=(e); ++x)
#define ALL(i) (i).begin(), (i).end()
#define CONTAINS(i,v) (find(ALL(i),v)!=(i).end())
typedef vector<bool> bit_vector;
typedef vector<int> int_vector;
typedef vector<uInt> VI;
typedef vector<ulLong> VLL;

#define MAX_T 300000

class PrzypadekTestowy
{
private:
	lLong _maxWyk;	
	FILE *_input;
	int _skarbonka[MAX_T];
	inline void Reset()
	{
		memset(_skarbonka, 0, sizeof(_skarbonka));
		_maxWyk = 0;
	}

	inline void WczytajInt(int *value)
	{
		fscanf(_input, "%d\n", value);
	}	
public:
	PrzypadekTestowy() :_input(stdin)
	{
	}
	PrzypadekTestowy(FILE *input)
	{
		_input = input;
	}

	inline void Wykonaj()
	{
		Reset();
		WczytajPrzypadekTestowy();
		Rozwiaz();
	}
	inline void Rozwiaz()
	{
		int i = 0, ile=0;

		// redukcja jednakowych wykladnikow do wykladnika o 1 wiekszego
		for (;i <= _maxWyk; i++)
		{			
			if (_skarbonka <= 0) continue;
			ile = _skarbonka[i];			
			if (ile < 2) continue; //za malo			
			_skarbonka[i + 1] += (ile >> 1); //przenies do kolejnego wykladnika
			_skarbonka[i] %= 2; //to jest raczej zbedne, teoretycznie mozna wyremowac
		}
		// kontynuacja juz poza skarbonka
		ile = _skarbonka[_maxWyk+1];
		while (ile > 0)
		{
			_maxWyk++;			
			ile = ile >> 1;
		}
		printf("%lld\n", _maxWyk);
	}

	inline void WczytajPrzypadekTestowy()
	{
		int n, a;		
		WczytajInt(&n);
		for (int i = 0; i < n; i++)
		{
			WczytajInt(&a);
			_skarbonka[a]++; //policz nominaly
			_maxWyk = _maxWyk<a?a:_maxWyk;
		}
	}
};

int main(int argc, char **argv)
{
	FILE *in = stdin;
	if (argc>1)
	{
		in = fopen(argv[1], "rt");
		if (NULL == in)
		{
			in = stdin;
		}
	}

	PrzypadekTestowy *p = new PrzypadekTestowy(in);
	p->Wykonaj();
	fclose(in);
	delete(p);
	return 0;
}