OI XXXIII - dys (Alt3)

// https://szkopul.edu.pl/problemset/problem/i1DZIWhPW7P03dKICkwxIB56/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

typedef __int128_t int128;
typedef unsigned __int128 uint128;

const long long MOD = 1000000007;

struct Pile {
    long long count;
    int index;
};

bool comparePiles(const Pile& a, const Pile& b) {
    return a.count > b.count;
}

int128 countBad(int128 D, uint128 mask) {
    if (D < 0) return 0;
    if (mask == 0) return D + 1;

    int max_bit = 0;
    int128 temp = D;
    while (temp > 0) {
        temp >>= 1;
        max_bit++;
    }

    int128 count = 0;

    int limit = max(max_bit, 65);

    vector<int> free_bits_below(limit + 1, 0);
    int current_free = 0;
    for (int i = 0; i <= limit; ++i) {
        free_bits_below[i] = current_free;
        if (!((mask >> i) & 1)) {
            current_free++;
        }
    }

    bool match_possible = true;
    for (int i = limit; i >= 0; --i) {
        bool d_bit = (D >> i) & 1;
        bool mask_bit = (mask >> i) & 1;

        if (d_bit) {
            count += ((int128)1 << free_bits_below[i]);

            if (mask_bit) {
                match_possible = false;
                break;
            }
        }
    }

    if (match_possible) count++;

    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<Pile> piles;
    piles.reserve(n);

    int128 max_days = 0;
    long long huge_res = -1;
    int huge_idx = -1;

    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        if (a == 0) continue;

        if (i + 1 > 62) {
            if (i + 1 > huge_idx) {
                huge_idx = i + 1;
                long long term1 = 1;
                long long base = 2;
                long long exp = i;
                while (exp > 0) {
                    if (exp % 2) term1 = (term1 * base) % MOD;
                    base = (base * base) % MOD;
                    exp /= 2;
                }
                huge_res = (term1 + (a % MOD) - 1 + MOD) % MOD;
            }
        } else {
            piles.push_back({a, i + 1});

            int128 p_val = ((int128)1) << i;
            int128 cycle = p_val * 2;
            int128 full_cycles = (a - 1) / p_val;
            int128 rem = a - full_cycles * p_val;
            int128 single_d = full_cycles * cycle + p_val + rem - 1;
            if (single_d > max_days) max_days = single_d;
        }
    }

    sort(piles.begin(), piles.end(), comparePiles);

    uint128 current_mask = 0;
    int128 current_sum = 0;

    for (const auto& p : piles) {
        current_sum += p.count;
        current_mask |= ((uint128)1 << (p.index - 1));

        int128 bad = countBad(max_days, current_mask) - 1;
        int128 good = max_days - bad;

        if (good >= current_sum) continue;

        int128 needed = current_sum - good;
        int128 low = max_days + 1;
        int128 high = max_days + needed * 2 + ((int128)1 << 16);
        if (high < current_sum * 2) high = current_sum * 2 + 1000;

        int128 ans = high;

        while (low <= high) {
            int128 mid = low + (high - low) / 2;
            int128 b = countBad(mid, current_mask) - 1;
            int128 g = mid - b;
            if (g >= current_sum) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        max_days = ans;
    }

    long long final_ans;
    if (huge_idx != -1) {
        int128 huge_start = ((int128)1) << (huge_idx - 1);
        final_ans = huge_res;
    } else {
        final_ans = (long long)(max_days % MOD);
    }

    cout << final_ans << "\n";

    return 0;
}