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
#include <cstdio>
#include <cmath>
#include <cassert> 
#include <string>
#include <algorithm>
#include <functional>
//#define DEBUG

#ifdef DEBUG
#define D(x); x
#else
#define D(x);
#endif

using namespace std;

int input[1000002];

void print_input(int n) {
  if(n > 50) 
    printf("[...]*%d ", n);
  else
    for(int i = 0; i < n; i++) {
      printf("%d ", input[i]);
    }
}

int max_coin(int n) {
  D(printf("---\nMAX COIN for array of (%d): ", n););
  sort(input, input + n, greater<int>());
  D(print_input(n););
  int m = input[0]; // max
  int uv = input[0]; // next upgrade - value needed
  int uq = 1; // next upgrade - quantity needed
  for(int i = 1; i < n; i++) {
    if(input[i] == uv) {
      uq--;
      if(uq == 0) {
        m++;
        int p = m - uv;
        if(p > 20) break;
        uq = (int)pow(2, p);
      }
    } else {
      // needed: uq * uv
      // now need: (nuq * input[i]) - 1 where input[i] < uv
      int nuq = (uv - input[i]) * 2 * uq;
      uq = nuq - 1;
      uv = input[i];
    }
  }

  D(printf("= %d\n", m););
  return m;
}

#ifdef DEBUG
int test(int a[], int n) {
  std::copy(a, a + n, input);
  return max_coin(n);
}

int main() {
  assert(test((int []){1, 2, 3, 4}, 4) == 4);
  assert(test((int []){0}, 1) == 0);
  assert(test((int []){1}, 1) == 1);
  assert(test((int []){2}, 1) == 2);
  assert(test((int []){201719}, 1) == 201719);
  assert(test((int []){201717, 201717, 201718}, 3) == 201719);
  assert(test((int []){201717, 201717, 201718, 1}, 4) == 201719);
  assert(test((int []){2, 2, 2, 2}, 4) == 4);
  assert(test((int []){1, 2, 2, 1, 2}, 5) == 4);
  assert(test((int []){1, 2, 0, 1, 2}, 5) == 3);
  assert(test((int []){4, 3}, 2) == 4);
  assert(test((int []){0, 0, 0, 0}, 4) == 2);
  assert(test((int []){1, 0, 1, 1, 1}, 5) == 3);
  assert(test((int []){4, 4, 4, 4, 4, 4, 4, 4, 4, 4}, 10) == 7);
  assert(test((int []){10, 7, 7, 7, 7, 7, 7, 7, 7, 7}, 10) == 11);

  int big[1000000];
  for(int i = 0; i < 1000000; i++) {
    big[i] = 1;
  }
  assert(test(big, 20) == 5);
  assert(test(big, 50) == 6);
  assert(test(big, 1000000) == 20);

  big[500] = 201717;
  big[1500] = 201717;
  big[999999] = 201718;
  assert(test(big, 1000000) == 201719);
  return 0;
}
#else
int main() {
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d", &input[i]);
  }
  printf("%d\n", max_coin(n));

  return 0;
}
#endif