QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799828#7930. Do It Yourself?ucup-team5062#AC ✓1811ms293756kbC++206.9kb2024-12-05 18:31:482024-12-05 18:31:49

Judging History

你现在查看的是最新测评结果

  • [2024-12-05 18:31:49]
  • 评测
  • 测评结果:AC
  • 用时:1811ms
  • 内存:293756kb
  • [2024-12-05 18:31:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// ===================================================================== RAQ & RMQ
struct Node {
    long long val, idx;
};

Node operator+(Node &a1, Node &a2) {
    return Node{a1.val + a2.val, a1.idx + a2.idx};
}

bool operator<(const Node &a1, const Node &a2) {
    if (a1.val < a2.val) return true;
    if (a1.val > a2.val) return false;
    if (a1.idx < a2.idx) return true;
    return false;
}

class SegmentTree {
public:
    int size_ = 1;
    vector<Node> dat;
    vector<Node> laz;

    void init(int sz) {
        while (size_ <= sz) size_ *= 2;
        dat.resize(size_ * 2, Node{(1LL << 60), 0LL});
        laz.resize(size_ * 2, Node{0LL, 0LL});
    }

    void refresh(int pos) {
        if (pos < size_) {
            laz[pos * 2 + 0] = laz[pos * 2 + 0] + laz[pos];
            laz[pos * 2 + 1] = laz[pos * 2 + 1] + laz[pos];
            laz[pos] = Node{0LL, 0LL};
            dat[pos] = min(dat[pos * 2 + 0] + laz[pos * 2 + 0], dat[pos * 2 + 1] + laz[pos * 2 + 1]);
        }
        else {
            dat[pos] = dat[pos] + laz[pos];
            laz[pos] = Node{0LL, 0LL};
        }
    }

    void add_(int l, int r, Node x, int a, int b, int u) {
        if (l <= a && b <= r) { laz[u] = laz[u] + x; return; }
        if (r <= a || b <= l) return;
        add_(l, r, x, a, (a + b) / 2, u * 2);
        add_(l, r, x, (a + b) / 2, b, u * 2 + 1);
        refresh(u);
    }

    void add(int l, int r, Node x) {
        add_(l, r, x, 0, size_, 1);
    }

    Node query_(int l, int r, int a, int b, int u) {
        if (l <= a && b <= r) return dat[u] + laz[u];
        if (r <= a || b <= l) return Node{(1LL << 60), -1LL};
        refresh(u);
        Node v1 = query_(l, r, a, (a + b) / 2, u * 2);
        Node v2 = query_(l, r, (a + b) / 2, b, u * 2 + 1);
        refresh(u);
        return min(v1, v2);
    }

    Node query(int l, int r) {
        return query_(l, r, 0, size_, 1);
    }
};


// ===================================================================== Main Part
long long N;
long long P[500009];
long long F[500009];
long long Count[500009];
set<int> G[500009];

// HLD Part
long long dp[500009];
long long Max_[500009];
long long Root[500009];
long long Indx[500009];
SegmentTree Z[500009];
SegmentTree All;
vector<int> Temp;

void Initialize() {
    for (int i = 0; i <= 200; i++) P[i] = 0;
    for (int i = 0; i <= 200; i++) F[i] = 0;
    for (int i = 0; i <= 200; i++) Count[i] = 0;
    for (int i = 0; i <= 200; i++) G[i].clear();
    for (int i = 0; i <= 200; i++) dp[i] = 0;
    for (int i = 0; i <= 200; i++) Max_[i] = 0;
    for (int i = 0; i <= 200; i++) Root[i] = 0;
    for (int i = 0; i <= 200; i++) Indx[i] = 0;
    for (int i = 0; i <= 200; i++) {
        Z[i].size_ = 1;
        Z[i].dat.clear();
        Z[i].laz.clear();
    }
    for (int i = 0; i <= 200; i++) {
        All.size_ = 1;
        All.dat.clear();
        All.laz.clear();
    }
    Temp.clear();
}

void dfs1(int pos) {
    dp[pos] = 1;
    for (int idx : G[pos]) {
        dfs1(idx);
        dp[pos] += dp[idx];
    }
}

void dfs2(int pos, int r, int c) {
    Root[pos] = r;
    Indx[pos] = c;
    Max_[r] = max(Max_[r], 1LL * c);
    pair<long long, int> maxn = make_pair(-1, -1);
    for (int idx : G[pos]) maxn = max(maxn, make_pair(dp[idx], idx));

    // Recursion
    for (int idx : G[pos]) {
        if (maxn.second == idx) {
            dfs2(idx, r, c + 1);
        }
        else {
            dfs2(idx, idx, 1);
        }
    }
}

void Delete(int pos) {
    All.add(pos, pos + 1, Node{(1LL << 60), 0});
    Z[Root[pos]].add(Indx[pos], Indx[pos] + 1, Node{(1LL << 60), 0});
    Temp.push_back(pos);
    for (int idx : G[pos]) Delete(idx);
}

void Search(int pos) {
    while (true) {
        Z[Root[pos]].add(1, Indx[pos] + 1, Node{-1LL, 0LL});
        while (true) {
            Node minv = Z[Root[pos]].query(0, Z[Root[pos]].size_);
            if (minv.val <= 0) {
                Temp.clear();
                Delete(minv.idx);
                for (int idx : Temp) {
                    if (idx != 1) G[P[idx]].erase(idx);
                }
            }
            else break;
        }
        if (Root[pos] == 1) break;
        pos = P[Root[pos]];
    }
}

// ============================================================================= Output Function
long long Solve_Outp() {
    for (int i = 2; i <= N; i++) G[P[i]].insert(i);

    // Step 2. Initialize
    dfs1(1);
    dfs2(1, 1, 1);
    All.init(N + 2);
    for (int i = 1; i <= N; i++) Z[i].init(Max_[i]);
    for (int i = 1; i <= N; i++) Z[Root[i]].add(Indx[i], Indx[i] + 1, Node{dp[i] - (1LL << 60), 1LL * i});
    for (int i = 1; i <= N; i++) {
        All.add(i, i + 1, Node{F[i] - (1LL << 60), 1LL * i});
    }

    // Step 3. Simulation
    long long Answer = 0;
    for (int loops = 1; loops <= N; loops++) {
        Node incr = All.query(0, All.size_);
        Answer += incr.val;
        Count[incr.idx] += 1;
        All.add(incr.idx, incr.idx + 1, Node{2LL * F[incr.idx], 0LL});
        Search(incr.idx);
    }
    return Answer;
}


// ============================================================================= Output Function
long long dfs4(int pos, vector<long long> c) {
    if (pos == N + 1) {
        long long sum = 0;
        for (int i = 1; i <= N; i++) sum += F[i] * c[i] * c[i];
        return sum;
    }
    int cx = pos; long long ret = (1LL << 60);
    while (true) {
        vector<long long> r = c;
        r[cx] += 1;
        ret = min(ret, dfs4(pos + 1, r));
        if (cx == 1) break;
        cx = P[cx];
    }
    return ret;
}

long long Solve_Jury() {
    return dfs4(1, vector<long long>(N + 1, 0));
}


int main() {
    int DEBUG = 1;
    if (DEBUG == 1) {
        scanf("%lld", &N);
        for (int i = 2; i <= N; i++) scanf("%lld", &P[i]);
        for (int i = 1; i <= N; i++) scanf("%lld", &F[i]);
        cout << Solve_Outp() << endl;
    }
    else {
        for (int t = 1; t <= 100000; t++) {
            Initialize();
            N = rand() % 7 + 2;
            for (int i = 2; i <= N; i++) P[i] = rand() % (i - 1) + 1;
            for (int i = 1; i <= N; i++) F[i] = rand() % 9 + 1;

            // Check
            long long J1 = Solve_Jury();
            long long J2 = Solve_Outp();
            if (t % 1 == 0) cout << t << " " << J1 << " " << J2 << endl;
            if (J1 != J2) {
                cout << "Wrong Answer on Test #" << t << endl;
                cout << "Jury = " << J1 << ", Output = " << J2 << endl;
                cout << N << endl;
                for (int i = 2; i <= N; i++) cout << P[i] << " "; cout << endl;
                for (int i = 1; i <= N; i++) cout << F[i] << " "; cout << endl;
                return 0;
            }
        }
        cout << "AC" << endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 65892kb

input:

4
1 1 2
1 1 1 1

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 8ms
memory: 63832kb

input:

4
1 1 2
1 10 10 10

output:

16

result:

ok single line: '16'

Test #3:

score: 0
Accepted
time: 9ms
memory: 65956kb

input:

4
1 1 2
1 2 4 8

output:

10

result:

ok single line: '10'

Test #4:

score: 0
Accepted
time: 1531ms
memory: 224260kb

input:

500000
1 2 3 1 4 4 7 8 2 4 10 3 4 6 14 9 4 1 19 14 21 4 17 15 25 10 8 18 5 1 21 21 9 17 11 34 30 20 18 9 1 22 8 30 2 2 45 20 19 22 14 10 13 50 52 41 51 9 50 48 25 39 28 51 11 15 58 29 66 33 55 30 69 11 49 26 33 29 24 11 33 34 83 74 45 62 11 42 57 39 64 12 83 45 41 33 67 48 27 13 14 49 3 20 45 99 47 ...

output:

207687563920604635

result:

ok single line: '207687563920604635'

Test #5:

score: 0
Accepted
time: 1464ms
memory: 224248kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 1 13 14 15 16 17 18 19 20 21 22 23 4 25 26 27 28 29 3 31 32 33 34 35 36 37 38 39 2 41 42 43 44 45 46 47 48 49 50 51 52 32 54 55 56 57 58 59 60 61 62 63 1 65 66 67 68 69 70 71 72 73 41 75 76 77 78 79 80 81 25 83 84 85 86 87 88 89 90 91 92 93 94 95 96 25 98 99 100 101 10...

output:

207236136583346408

result:

ok single line: '207236136583346408'

Test #6:

score: 0
Accepted
time: 1561ms
memory: 224404kb

input:

500000
1 1 1 1 1 1 1 1 1 1 1 2 11 12 9 8 9 10 7 2 5 7 12 7 4 6 7 6 2 12 12 9 5 10 9 10 7 2 10 6 12 8 2 12 4 12 6 4 7 9 10 6 4 6 9 10 8 10 2 9 8 10 2 4 3 2 10 6 10 12 11 10 5 2 6 6 6 12 10 5 2 8 6 7 9 9 5 4 2 7 11 4 2 10 5 7 2 5 7 10 2 12 6 9 10 12 3 9 7 5 79 94 84 109 38 40 20 20 88 41 95 94 91 70 1...

output:

208664310591919367

result:

ok single line: '208664310591919367'

Test #7:

score: 0
Accepted
time: 1593ms
memory: 224212kb

input:

500000
1 1 2 4 1 1 3 6 8 10 9 4 6 14 7 6 13 7 6 5 7 8 5 23 23 1 15 27 15 21 5 32 23 32 25 15 36 29 24 2 19 31 16 28 35 22 13 12 37 2 42 21 49 49 55 34 55 32 43 33 51 40 28 1 20 44 4 1 44 66 22 57 20 14 63 55 15 38 74 6 1 10 39 84 78 13 26 84 40 26 9 65 78 27 76 44 85 1 76 30 37 93 97 14 41 21 50 29 ...

output:

209042548290179675

result:

ok single line: '209042548290179675'

Test #8:

score: 0
Accepted
time: 1577ms
memory: 224540kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 19 20 21 22 23 24 25 26 27 28 2 30 31 32 33 34 35 36 37 38 39 40 41 20 43 44 45 46 47 32 49 50 51 52 53 54 55 19 57 58 59 60 61 62 63 64 65 66 2 68 69 70 71 72 73 74 75 76 77 78 79 1 81 82 83 84 85 86 87 88 89 90 91 58 93 94 95 96 97 98 99 100 101 1...

output:

208018638981625638

result:

ok single line: '208018638981625638'

Test #9:

score: 0
Accepted
time: 1565ms
memory: 224412kb

input:

500000
1 1 1 1 1 1 1 1 1 1 10 6 2 3 6 2 4 4 4 5 9 6 6 3 4 7 8 2 7 5 4 4 3 7 9 8 4 5 6 8 3 5 10 5 10 9 9 4 10 7 2 7 4 2 4 2 11 6 6 2 6 6 8 6 2 6 6 6 4 4 7 6 10 4 4 7 20 61 19 74 59 73 53 52 17 65 69 61 24 69 35 73 13 59 49 59 75 38 75 47 59 62 26 63 17 57 59 61 32 45 65 62 57 71 69 59 18 42 24 26 73 ...

output:

208334616769818537

result:

ok single line: '208334616769818537'

Test #10:

score: 0
Accepted
time: 1507ms
memory: 224156kb

input:

500000
1 2 1 1 5 4 7 3 2 9 2 2 13 12 8 11 7 12 12 15 7 2 3 3 3 13 15 24 17 28 1 27 2 16 18 3 31 2 30 34 41 30 10 1 23 16 42 16 29 50 38 17 33 24 24 19 47 41 44 41 4 39 24 27 51 29 32 18 49 12 47 52 50 16 27 18 61 17 62 20 74 63 49 61 47 81 49 13 70 30 91 44 59 12 26 7 41 50 61 13 56 95 51 38 19 98 8...

output:

209848362394883100

result:

ok single line: '209848362394883100'

Test #11:

score: 0
Accepted
time: 1472ms
memory: 224320kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 19 20 21 22 23 24 25 26 27 28 29 30 31 32 2 34 35 36 37 38 39 40 41 42 43 44 23 46 47 48 49 50 51 3 53 54 55 56 57 58 59 60 61 62 22 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 2 82 83 84 85 86 87 88 89 90 46 92 93 94 95 96 97 98 99 100 101 1...

output:

209637349943341963

result:

ok single line: '209637349943341963'

Test #12:

score: 0
Accepted
time: 1571ms
memory: 224180kb

input:

500000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 17 17 17 17 3 14 10 17 17 17 13 16 9 16 5 16 9 12 3 3 16 13 13 4 5 10 4 10 15 13 16 14 11 12 8 5 13 13 17 9 14 17 3 10 3 9 12 14 17 10 9 3 17 14 3 3 4 9 17 10 16 16 16 10 17 9 16 15 5 9 9 3 4 13 9 6 5 5 14 4 9 9 12 5 8 10 67 30 31 50 95 86 106 26 85 60 2...

output:

209117719378085009

result:

ok single line: '209117719378085009'

Test #13:

score: 0
Accepted
time: 1434ms
memory: 222692kb

input:

500000
1 1 1 2 3 3 4 7 8 2 1 5 3 5 2 2 11 16 14 2 20 19 22 13 7 26 23 15 2 6 8 11 28 29 16 19 1 29 27 33 17 36 28 12 20 26 2 1 9 8 1 17 22 14 8 26 19 36 39 47 34 14 50 51 29 37 24 68 51 25 46 3 41 45 66 28 29 71 18 52 79 55 29 8 76 5 4 67 15 88 77 84 32 90 18 83 43 97 29 87 59 77 35 43 10 78 2 32 26...

output:

911766231

result:

ok single line: '911766231'

Test #14:

score: 0
Accepted
time: 1339ms
memory: 222784kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 3 13 14 15 16 17 1 19 20 21 22 23 24 25 26 27 28 29 30 20 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 20 49 50 51 52 53 54 55 56 57 58 59 2 61 62 63 64 65 66 67 68 69 70 71 72 32 74 75 76 77 78 79 80 81 82 32 84 85 86 87 88 89 90 91 92 74 94 95 96 97 98 33 100 101 ...

output:

1341960955

result:

ok single line: '1341960955'

Test #15:

score: 0
Accepted
time: 1304ms
memory: 222628kb

input:

500000
1 1 1 1 1 1 1 1 1 1 1 1 1 10 10 7 14 11 4 6 11 13 12 5 6 11 8 3 5 4 7 11 11 10 4 2 6 7 3 14 5 4 14 4 6 4 6 4 10 4 5 12 8 11 2 6 10 14 11 3 4 11 8 7 4 11 4 8 7 2 5 10 7 10 11 8 8 11 4 7 5 11 12 5 3 10 3 14 8 13 7 11 3 11 4 6 13 10 7 74 52 62 69 66 27 23 86 50 47 69 89 91 19 41 75 90 35 58 96 9...

output:

13124595491

result:

ok single line: '13124595491'

Test #16:

score: 0
Accepted
time: 1428ms
memory: 224112kb

input:

500000
1 2 2 2 4 3 5 4 2 1 10 6 8 14 10 10 2 8 11 19 21 12 1 5 3 19 17 8 17 27 15 2 12 12 13 1 28 3 35 33 14 1 12 14 29 40 13 17 33 43 50 52 47 40 8 8 22 23 37 1 9 47 41 2 54 43 54 24 21 20 11 6 21 38 6 76 51 41 36 55 33 32 81 75 24 65 20 84 41 62 5 47 1 33 39 46 69 57 80 74 11 14 31 84 95 32 54 26 ...

output:

52527295851455608

result:

ok single line: '52527295851455608'

Test #17:

score: 0
Accepted
time: 1420ms
memory: 224256kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 3 15 16 17 18 19 20 21 22 23 24 25 26 27 2 29 30 31 32 33 34 35 36 37 38 39 16 41 42 43 44 45 46 47 48 49 50 3 52 53 54 55 56 57 58 59 60 61 30 63 64 65 66 67 68 69 70 1 72 73 74 75 76 77 78 79 80 73 82 83 84 85 86 87 88 1 90 91 92 93 94 95 96 97 98 99 100 101 10...

output:

50307007224044341

result:

ok single line: '50307007224044341'

Test #18:

score: 0
Accepted
time: 1397ms
memory: 224188kb

input:

500000
1 1 1 1 1 1 1 1 1 5 5 4 9 4 3 3 10 4 5 4 9 3 5 4 8 7 7 5 5 10 6 4 4 4 4 10 5 5 4 3 2 5 7 4 7 3 10 5 7 38 36 20 48 24 11 45 45 38 20 41 12 24 35 19 24 19 12 35 38 21 37 23 43 19 30 42 48 11 19 18 29 36 46 45 43 43 22 11 25 31 11 24 29 20 36 18 39 43 18 39 20 45 24 45 24 34 21 27 24 43 19 13 36...

output:

54161418282241609

result:

ok single line: '54161418282241609'

Test #19:

score: 0
Accepted
time: 1502ms
memory: 224192kb

input:

500000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

198924785718011004

result:

ok single line: '198924785718011004'

Test #20:

score: 0
Accepted
time: 1565ms
memory: 224188kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 19 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 3 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 2 67 68 69 70 71 72 73 74 75 76 77 78 79 80 20 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 38 98 99 100 101 ...

output:

199365088144327247

result:

ok single line: '199365088144327247'

Test #21:

score: 0
Accepted
time: 1663ms
memory: 224308kb

input:

500000
1 1 2 2 3 3 5 6 5 4 7 7 4 6 10 14 8 9 11 9 15 13 14 12 13 10 8 8 11 12 15 30 17 23 16 29 20 18 29 26 19 25 20 24 31 30 31 23 22 19 27 22 24 21 27 24 16 22 21 23 26 25 31 32 17 32 18 57 44 53 60 42 35 64 65 43 35 51 39 66 38 63 37 64 36 39 38 61 43 61 59 34 56 59 45 66 46 67 56 34 45 58 53 59 ...

output:

199321991323850955

result:

ok single line: '199321991323850955'

Test #22:

score: 0
Accepted
time: 1335ms
memory: 220912kb

input:

500000
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20 21 21 21 21 21 22 22 22 22 22 23 23 23...

output:

221838298151100225

result:

ok single line: '221838298151100225'

Test #23:

score: 0
Accepted
time: 1497ms
memory: 220912kb

input:

500000
1 2 3 4 5 6 7 8 1 10 11 12 13 14 15 16 1 18 19 20 21 22 23 24 1 26 27 28 29 30 31 27 33 34 35 36 37 26 39 40 41 42 43 44 2 46 47 48 49 50 51 26 53 54 55 56 57 58 2 60 61 62 63 64 26 66 67 68 69 70 71 54 73 74 75 76 18 78 79 80 81 82 83 1 85 86 87 88 89 90 91 10 93 94 95 96 97 98 79 100 101 10...

output:

221214676949285229

result:

ok single line: '221214676949285229'

Test #24:

score: 0
Accepted
time: 1512ms
memory: 220984kb

input:

500000
1 1 1 1 1 5 2 6 3 4 3 6 5 2 4 2 2 3 6 3 5 4 4 2 3 4 6 6 5 5 23 18 30 27 13 27 30 25 8 18 22 9 17 22 27 29 24 29 21 13 31 16 30 7 21 30 28 17 14 8 26 14 11 17 16 28 30 13 25 31 20 19 11 25 24 11 21 9 9 9 7 31 23 23 15 31 26 29 14 20 10 23 21 13 27 26 9 14 8 19 8 28 25 10 29 12 10 27 24 28 19 2...

output:

221237625564207541

result:

ok single line: '221237625564207541'

Test #25:

score: 0
Accepted
time: 1159ms
memory: 222420kb

input:

500000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

607359786

result:

ok single line: '607359786'

Test #26:

score: 0
Accepted
time: 1372ms
memory: 223988kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 2 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 1 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 51 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 53 84 85 86 87 88 89 90 91 92 93 94 95 96 97 52 99 100 101 ...

output:

889638320

result:

ok single line: '889638320'

Test #27:

score: 0
Accepted
time: 1486ms
memory: 222780kb

input:

500000
1 1 1 4 4 2 2 2 5 8 6 6 5 8 6 7 7 15 10 18 16 14 16 18 11 17 10 11 17 13 14 15 14 13 14 35 22 28 27 21 29 23 19 25 32 19 31 23 22 27 22 24 32 28 29 30 20 31 31 33 30 29 24 26 20 33 21 35 25 26 40 54 55 61 61 49 51 41 54 53 50 62 50 69 46 39 56 55 57 56 71 64 39 60 68 43 49 51 63 65 58 64 48 6...

output:

649599065

result:

ok single line: '649599065'

Test #28:

score: 0
Accepted
time: 1377ms
memory: 224068kb

input:

500000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

50098762057260484

result:

ok single line: '50098762057260484'

Test #29:

score: 0
Accepted
time: 1470ms
memory: 224092kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 19 20 21 22 23 24 25 26 27 28 29 30 31 1 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 4 51 52 53 54 55 56 57 58 59 60 61 62 63 64 20 66 67 68 69 70 33 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 67 89 90 91 92 93 94 95 96 97 98 99 7 101 10...

output:

48134202909769814

result:

ok single line: '48134202909769814'

Test #30:

score: 0
Accepted
time: 1557ms
memory: 224344kb

input:

500000
1 1 2 3 2 3 6 7 5 7 6 4 6 5 4 9 15 8 14 13 8 9 13 15 11 9 11 14 10 16 10 16 21 22 27 28 30 31 33 25 18 20 25 24 23 32 19 27 33 26 22 32 23 31 24 29 30 29 25 21 19 20 26 30 28 24 18 44 51 47 49 39 64 36 47 35 47 46 36 63 61 58 66 65 46 40 37 51 62 60 54 57 43 66 57 43 47 53 48 42 35 53 44 45 3...

output:

50295562646770328

result:

ok single line: '50295562646770328'

Test #31:

score: 0
Accepted
time: 1008ms
memory: 221152kb

input:

500000
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20 21 21 21 21 21 22 22 22 22 22 23 23 23...

output:

938164918

result:

ok single line: '938164918'

Test #32:

score: 0
Accepted
time: 1389ms
memory: 220088kb

input:

500000
1 2 3 4 5 6 7 1 9 10 11 12 13 14 15 1 17 18 19 20 21 22 17 24 25 26 27 28 29 1 31 32 33 34 35 36 2 38 39 40 41 42 43 1 45 46 47 48 49 50 51 24 53 54 55 56 57 31 59 60 61 62 63 17 65 66 67 68 31 70 71 72 73 74 75 45 77 78 79 80 81 82 4 84 85 86 87 17 89 90 91 92 9 94 95 96 97 98 99 10 101 102 ...

output:

1455720357

result:

ok single line: '1455720357'

Test #33:

score: 0
Accepted
time: 1355ms
memory: 219636kb

input:

500000
1 1 1 1 1 4 4 4 5 5 5 3 5 6 3 2 3 6 2 4 2 3 2 6 3 2 6 5 4 6 24 31 22 13 10 21 9 14 12 9 16 20 27 27 7 28 27 13 18 18 24 19 19 29 8 24 22 30 14 11 9 27 31 8 13 25 17 23 31 30 26 11 19 20 15 10 24 28 19 25 16 29 21 25 21 29 16 22 26 15 26 11 20 31 16 12 7 23 17 29 17 15 24 21 7 8 7 16 19 29 14 ...

output:

908009754

result:

ok single line: '908009754'

Test #34:

score: 0
Accepted
time: 1198ms
memory: 220792kb

input:

500000
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20 21 21 21 21 21 22 22 22 22 22 23 23 23...

output:

56304937802706991

result:

ok single line: '56304937802706991'

Test #35:

score: 0
Accepted
time: 1442ms
memory: 220776kb

input:

500000
1 2 3 4 5 6 7 8 1 10 11 12 13 14 1 16 17 18 19 20 21 1 23 24 25 26 27 28 29 24 31 32 33 34 35 10 37 38 39 40 41 42 16 44 45 46 47 48 49 17 51 52 53 54 11 56 57 58 59 60 16 62 63 64 65 66 67 2 69 70 71 72 73 74 23 76 77 78 79 80 81 1 83 84 85 86 87 88 89 12 91 92 93 16 95 96 97 98 99 100 2 102...

output:

54276526062834250

result:

ok single line: '54276526062834250'

Test #36:

score: 0
Accepted
time: 1463ms
memory: 220820kb

input:

500000
1 1 1 1 1 4 3 5 4 3 3 5 2 4 5 6 2 6 4 4 6 5 2 2 5 5 4 2 3 6 3 6 28 24 15 18 23 12 9 10 28 16 26 7 8 7 30 27 29 29 30 24 12 28 19 11 11 8 7 17 19 14 18 24 16 12 7 18 32 29 15 33 25 12 31 24 10 32 25 19 26 10 31 22 15 14 26 16 22 33 25 24 11 26 31 15 32 8 9 14 17 8 26 10 7 28 10 25 27 19 32 30 ...

output:

55741612083767159

result:

ok single line: '55741612083767159'

Test #37:

score: 0
Accepted
time: 1174ms
memory: 236708kb

input:

500000
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 1...

output:

49085430970968434

result:

ok single line: '49085430970968434'

Test #38:

score: 0
Accepted
time: 1138ms
memory: 237936kb

input:

500000
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 1...

output:

46897090706805357

result:

ok single line: '46897090706805357'

Test #39:

score: 0
Accepted
time: 1255ms
memory: 258932kb

input:

500000
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 1...

output:

49286066388339149

result:

ok single line: '49286066388339149'

Test #40:

score: 0
Accepted
time: 1224ms
memory: 228336kb

input:

500000
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 1...

output:

68106582658510676

result:

ok single line: '68106582658510676'

Test #41:

score: 0
Accepted
time: 1286ms
memory: 228412kb

input:

500000
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 1...

output:

68558887051333395

result:

ok single line: '68558887051333395'

Test #42:

score: 0
Accepted
time: 1811ms
memory: 228944kb

input:

500000
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 48 49 50 52 51 54 53 55 56 57 58 59 60 61 62 64 63 66 65 67 68 69 70 72 71 74 73 75 76 78 77 79 80 81 82 83 84 85 86 88 87 90 89 91 92 93 94 95 96 98 97 100 9...

output:

68295034316204849

result:

ok single line: '68295034316204849'

Test #43:

score: 0
Accepted
time: 922ms
memory: 253876kb

input:

500000
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 1...

output:

648118955

result:

ok single line: '648118955'

Test #44:

score: 0
Accepted
time: 906ms
memory: 251460kb

input:

500000
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 1...

output:

442382895

result:

ok single line: '442382895'

Test #45:

score: 0
Accepted
time: 1116ms
memory: 261684kb

input:

500000
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 1...

output:

270556199

result:

ok single line: '270556199'

Test #46:

score: 0
Accepted
time: 1092ms
memory: 243424kb

input:

500000
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 1...

output:

22704436112612338

result:

ok single line: '22704436112612338'

Test #47:

score: 0
Accepted
time: 1066ms
memory: 240000kb

input:

500000
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 1...

output:

22392543248317695

result:

ok single line: '22392543248317695'

Test #48:

score: 0
Accepted
time: 1080ms
memory: 243428kb

input:

500000
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 1...

output:

22701903112969018

result:

ok single line: '22701903112969018'

Test #49:

score: 0
Accepted
time: 969ms
memory: 229528kb

input:

500000
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 1...

output:

484571798

result:

ok single line: '484571798'

Test #50:

score: 0
Accepted
time: 1000ms
memory: 227924kb

input:

500000
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 1...

output:

469022518

result:

ok single line: '469022518'

Test #51:

score: 0
Accepted
time: 1501ms
memory: 230304kb

input:

500000
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 1...

output:

1037656276

result:

ok single line: '1037656276'

Test #52:

score: 0
Accepted
time: 1166ms
memory: 228292kb

input:

500000
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 1...

output:

23515360087040309

result:

ok single line: '23515360087040309'

Test #53:

score: 0
Accepted
time: 1165ms
memory: 229776kb

input:

500000
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 1...

output:

22784608135182625

result:

ok single line: '22784608135182625'

Test #54:

score: 0
Accepted
time: 1489ms
memory: 229880kb

input:

500000
1 2 2 4 4 3 7 6 5 9 8 10 12 13 11 16 14 15 18 19 17 22 21 20 23 24 25 27 26 28 31 30 29 33 34 32 35 36 37 39 40 38 43 42 41 45 46 44 47 48 49 50 52 51 53 54 55 57 56 58 59 60 61 63 64 62 66 65 67 68 70 69 71 72 73 76 74 75 77 78 79 82 80 81 84 83 85 88 87 86 86 91 89 92 90 93 95 96 94 99 100 ...

output:

23475547631668249

result:

ok single line: '23475547631668249'

Test #55:

score: 0
Accepted
time: 1125ms
memory: 223564kb

input:

500000
1 2 3 1 1 4 7 6 1 3 8 2 6 1 14 13 7 13 7 5 19 14 21 13 5 15 20 27 28 10 6 21 12 25 22 33 37 14 30 29 36 26 18 4 37 24 40 15 48 24 19 32 51 36 24 19 51 49 41 50 13 32 27 9 59 41 19 14 26 58 32 13 71 26 3 63 53 2 11 68 50 63 53 70 49 37 13 64 30 68 63 26 25 81 2 91 97 30 86 53 70 19 62 80 15 12...

output:

1227856

result:

ok single line: '1227856'

Test #56:

score: 0
Accepted
time: 1335ms
memory: 222268kb

input:

500000
1 1 1 2 1 1 4 8 6 4 7 12 13 3 4 4 11 18 9 10 11 15 12 1 25 1 19 2 25 10 24 13 31 6 22 21 1 6 16 40 13 19 27 34 23 19 16 11 42 20 13 26 48 2 14 7 28 57 43 24 31 25 8 27 39 45 44 25 7 30 31 72 66 70 2 66 74 48 10 32 79 40 6 30 1 4 27 5 76 54 78 86 62 77 32 45 45 62 1 57 86 45 43 78 53 97 47 62 ...

output:

5343313

result:

ok single line: '5343313'

Test #57:

score: 0
Accepted
time: 844ms
memory: 293756kb

input:

500000
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 1...

output:

3504484

result:

ok single line: '3504484'

Test #58:

score: 0
Accepted
time: 1054ms
memory: 248284kb

input:

499999
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 1...

output:

44333375810119546

result:

ok single line: '44333375810119546'

Test #59:

score: 0
Accepted
time: 1304ms
memory: 234392kb

input:

500000
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 1...

output:

100574647700021650

result:

ok single line: '100574647700021650'

Test #60:

score: 0
Accepted
time: 1751ms
memory: 237736kb

input:

499999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 36 48 21 26 23 40 31 22 44 35 37 34 38 24 33 32 45 46 19 41 42 47 20 43 29 28 27 25 39 30 77 60 72 69 49 53 54 64 55 59 63 71 74 78 52 75 56 68 66 51 61 62 67 76...

output:

153310229302065909

result:

ok single line: '153310229302065909'

Test #61:

score: 0
Accepted
time: 877ms
memory: 253316kb

input:

500000
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 1...

output:

6546975658060

result:

ok single line: '6546975658060'

Test #62:

score: 0
Accepted
time: 1027ms
memory: 241172kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 4 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 52 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...

output:

176221993678

result:

ok single line: '176221993678'

Test #63:

score: 0
Accepted
time: 1459ms
memory: 235980kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 43 22 47 28 45 36 30 35 34 21 37 48 33 23 32 25 42 39 38 46 27 26 20 40 49 24 29 41 31 44 61 73 60 54 51 65 75 64 68 62 78 59 72 57 74 66 76 79 69 70 58 55 53...

output:

1167793245

result:

ok single line: '1167793245'

Test #64:

score: 0
Accepted
time: 1029ms
memory: 234236kb

input:

500000
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 1...

output:

22039824539765862

result:

ok single line: '22039824539765862'

Test #65:

score: 0
Accepted
time: 1205ms
memory: 234652kb

input:

500000
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 4 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 10...

output:

22569180334831618

result:

ok single line: '22569180334831618'

Test #66:

score: 0
Accepted
time: 1402ms
memory: 237512kb

input:

500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 36 40 41 24 45 29 30 34 31 33 39 46 22 27 42 32 21 25 49 26 37 38 35 28 44 23 20 43 48 47 56 64 51 67 76 57 79 71 60 78 55 72 77 66 65 75 59 70 62 68 73 58 50...

output:

46719641642743136

result:

ok single line: '46719641642743136'

Test #67:

score: 0
Accepted
time: 4ms
memory: 66116kb

input:

2
1
1 1

output:

2

result:

ok single line: '2'

Test #68:

score: 0
Accepted
time: 4ms
memory: 63828kb

input:

2
1
6051058061 661616852543

output:

24204232244

result:

ok single line: '24204232244'

Test #69:

score: 0
Accepted
time: 4ms
memory: 63780kb

input:

2
1
404526197124 4886756431

output:

409412953555

result:

ok single line: '409412953555'

Test #70:

score: 0
Accepted
time: 1376ms
memory: 215508kb

input:

500000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

250241572597676030

result:

ok single line: '250241572597676030'

Test #71:

score: 0
Accepted
time: 1334ms
memory: 215956kb

input:

500000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

248009672347165925

result:

ok single line: '248009672347165925'

Test #72:

score: 0
Accepted
time: 1456ms
memory: 232316kb

input:

500000
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 1...

output:

91866842863676203

result:

ok single line: '91866842863676203'

Test #73:

score: 0
Accepted
time: 1314ms
memory: 231568kb

input:

500000
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 1...

output:

170141648007448

result:

ok single line: '170141648007448'

Test #74:

score: 0
Accepted
time: 1654ms
memory: 233024kb

input:

500000
1 1 3 2 4 5 7 6 9 8 11 10 12 13 14 15 17 16 18 19 21 20 23 22 24 25 27 26 28 29 30 31 32 33 34 35 37 36 38 39 41 40 42 43 45 44 47 46 48 49 51 50 53 52 55 54 57 56 58 59 60 61 62 63 64 65 67 66 69 68 70 71 73 72 75 74 76 77 79 78 80 81 82 83 84 85 86 87 88 89 91 90 92 93 95 94 97 96 99 98 100...

output:

212724556216

result:

ok single line: '212724556216'