QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#484885#8712. Flooding Wallfractal70 1687ms711312kbC++177.1kb2024-07-20 04:34:442024-07-20 04:34:45

Judging History

This is the latest submission verdict.

  • [2024-07-20 04:34:45]
  • Judged
  • Verdict: 70
  • Time: 1687ms
  • Memory: 711312kb
  • [2024-07-20 04:34:44]
  • Submitted

answer

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

#define F first
#define S second 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());


typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 2e6 + 200;
const int M = 2e6 + 100;
const int inf = 2e9 + 3;
const ll INF = 1e18;

template<int mod>
class Modular {
public:
    int val;
    Modular() : val(0) {}
    Modular(int new_val) : val(new_val) {}
    // Modular(long long new_val) : val(new_val % mod) {}  // AFFECTS OPERATOR* (because it has one more %)
    friend Modular operator+(const Modular& a, const Modular& b) {
        if (a.val + b.val >= mod) return a.val + b.val - mod;
        else return a.val + b.val;
    }
    friend Modular operator-(const Modular& a, const Modular& b) {
        if (a.val - b.val < 0) return a.val - b.val + mod;
        else return a.val - b.val;
    }
    friend Modular operator*(const Modular& a, const Modular& b) {
        return 1ll * a.val * b.val % mod;
    }
    friend Modular binpow(Modular a, long long n) {
        Modular res = 1;
        for (; n; n >>= 1) {
            if (n & 1) res *= a;
            a *= a;
        }
        return res;
    }
    /* ALTERNATIVE INVERSE FUNCTION USING EXTENDED EUCLIDEAN ALGORITHM
    friend void gcd(int a, int b, Modular& x, Modular& y) {
        if (a == 0) {
            x = Modular(0);
            y = Modular(1);
            return;
        }
        Modular x1, y1;
        gcd(b % a, a, x1, y1);
        x = y1 - (b / a) * x1;
        y = x1;
    }
    friend Modular inv(const Modular& a) {
        Modular x, y;
        gcd(a.val, mod, x, y);
        return x;
    }
    */
    friend Modular inv(const Modular& a) {
        return binpow(a, mod - 2);
    }
    Modular operator/(const Modular& ot) const {
        return *this * inv(ot);
    }
    Modular& operator++() {
        if (val + 1 == mod) val = 0;
        else ++val;
        return *this;
    }
    Modular operator++(int) {
        Modular tmp = *this;
        ++(*this);
        return tmp;
    }
    Modular operator+() const {
        return *this;
    }
    Modular operator-() const {
        return 0 - *this;
    }
    Modular& operator+=(const Modular& ot) {
        return *this = *this + ot;
    }
    Modular& operator-=(const Modular& ot) {
        return *this = *this - ot;
    }
    Modular& operator*=(const Modular& ot) {
        return *this = *this * ot;
    }
    Modular& operator/=(const Modular& ot) {
        return *this = *this / ot;
    }
    bool operator==(const Modular& ot) const {
        return val == ot.val;
    }
    bool operator!=(const Modular& ot) const {
        return val != ot.val;
    }
    bool operator<(const Modular& ot) const {
        return val < ot.val;
    }
    bool operator>(const Modular& ot) const {
        return val > ot.val;
    }
    explicit operator int() const {
        return val;
    }
};
 
template<int mod>
istream& operator>>(istream& istr, Modular<mod>& x) {
    return istr >> x.val;
}
 
template<int mod>
ostream& operator<<(ostream& ostr, const Modular<mod>& x) {
    return ostr << x.val;
}
 
const int mod = 1e9 + 7;
using Mint = Modular<mod>;

struct node {
    int l, r;
    Mint sum, sumH;
    Mint p;

    node() {
        l = r = 0;
        p = 1;
        sum = sumH = 0;
    }
} t[N << 4];
int sz = 0;

vector<int> e = {0};

void push(int v, int tl, int tr) {
    if (t[v].p == 1) return;
    if (tl != tr) {
        t[v].l = (t[v].l ? t[v].l : ++sz);
        t[v].r = (t[v].r ? t[v].r : ++sz);
        t[t[v].l].p *= t[v].p;
        t[t[v].r].p *= t[v].p;
    }
    t[v].sum *= t[v].p;
    t[v].sumH *= t[v].p;
    t[v].p = 1;
}

void upd_mul(int l, int r, Mint val, int v = 1, int tl = 0, int tr = M) {
    push(v, tl, tr);
    if (l <= tl && tr <= r) {
        t[v].p *= val;
        push(v, tl, tr);
        return;
    }
    if (r < tl || tr < l)
        return;
    int tm = tl + tr >> 1;
    t[v].l = (t[v].l ? t[v].l : ++sz);
    t[v].r = (t[v].r ? t[v].r : ++sz);
    upd_mul(l, r, val, t[v].l, tl, tm);
    upd_mul(l, r, val, t[v].r, tm + 1, tr);
    t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
    t[v].sumH = t[t[v].l].sumH + t[t[v].r].sumH;
}

void upd(int pos, Mint val, int v = 1, int tl = 0, int tr = M) {
    push(v, tl, tr);
    if (tr < pos || tl > pos) return;
    if (tl == tr) {
        t[v].sum += val;
        if (tl < e.size()) 
            t[v].sumH += val * Mint(e[tl]);
        return;
    }
    int tm = tl + tr >> 1;
    t[v].l = (t[v].l ? t[v].l : ++sz);
    upd(pos, val, t[v].l, tl, tm);
    t[v].r = (t[v].r ? t[v].r : ++sz);
    upd(pos, val, t[v].r, tm + 1, tr);
    t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
    t[v].sumH = t[t[v].l].sumH + t[t[v].r].sumH;
}

Mint get(int l, int r, int v = 1, int tl = 0, int tr = M) {
    push(v, tl, tr);
    if (r < tl || tr < l || v == 0)
        return 0;
    if (l <= tl && tr <= r)
        return t[v].sum;
    int tm = tl + tr >> 1;
    return get(l, r, t[v].l, tl, tm) + get(l, r, t[v].r, tm + 1, tr);
}

Mint getH(int l, int r, int v = 1, int tl = 0, int tr = M) {
    push(v, tl, tr);
    if (r < tl || tr < l || v == 0)
        return 0;
    if (l <= tl && tr <= r)
        return t[v].sumH;
    int tm = tl + tr >> 1;
    return getH(l, r, t[v].l, tl, tm) + getH(l, r, t[v].r, tm + 1, tr);
}

int a[N + 1], b[N + 1];
Mint A[4][N + 1], B[4][N + 1], pw[N + 1];

int pos(int x) {
    return lower_bound(all(e), x) - e.begin();
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    pw[0] = 1;
    Mint ans = 0;
    for (int i = 1; i <= n; ++i) {
        pw[i] = pw[i - 1] * Mint(2);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ans = ans - Mint(a[i]) * pw[n - 1];
        e.push_back(a[i]);
        e.push_back(a[i] - 1);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        ans = ans - Mint(b[i]) * pw[n - 1];
        e.push_back(b[i]);
        e.push_back(b[i] - 1);
    }
    make_unique(e);
    ++sz;
    upd(0, 1);
    for (int i = 1; i <= n; ++i) {
        if (a[i] > b[i]) swap(a[i], b[i]);
        A[1][i] = get(0, pos(a[i] - 1));
        B[0][i] = get(0, pos(b[i]));
        upd(pos(a[i]), A[1][i]);
        upd(pos(b[i]), B[0][i]);
        upd_mul(0, pos(a[i] - 1), 0);
        upd_mul(pos(b[i] + 1), M, 2);
        ans = ans + getH(0, M) * pw[n - i];
        if (i == n) {
            ans = ans - getH(0, M) * Mint(n);
        }
    }
    upd_mul(0, M, 0);
    upd(0, 1);
    for (int i = n; i >= 1; --i) {
        A[3][i] = get(0, pos(a[i] - 1));
        B[2][i] = get(0, pos(b[i]));
        upd(pos(a[i]), A[3][i]);
        upd(pos(b[i]), B[2][i]);
        upd_mul(0, pos(a[i] - 1), 0);
        upd_mul(pos(b[i] + 1), M, 2);
        ans = ans + getH(0, M) * pw[i - 1];
    }
    cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 47ms
memory: 700764kb

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 55ms
memory: 699788kb

input:

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

output:

21116

result:

ok single line: '21116'

Test #3:

score: 0
Accepted
time: 24ms
memory: 699836kb

input:

1
1
2

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 51ms
memory: 700184kb

input:

2
1 1
2 2

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 40ms
memory: 700420kb

input:

3
1 1 1
2 2 2

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 51ms
memory: 699932kb

input:

3
1 1 1
3 2 3

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 59ms
memory: 699776kb

input:

3
2 1 1
3 2 3

output:

4

result:

ok single line: '4'

Test #8:

score: 0
Accepted
time: 48ms
memory: 699832kb

input:

3
1 1 2
3 2 3

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 47ms
memory: 699240kb

input:

4
1 1 2 2
2 2 1 1

output:

6

result:

ok single line: '6'

Test #10:

score: 0
Accepted
time: 31ms
memory: 700156kb

input:

3
1 4 4
3 1 1

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Accepted
time: 43ms
memory: 700552kb

input:

20
801072306 297281669 94099424 745640358 822582129 579751930 776707816 425952653 529794053 256263083 615445445 401366545 990263003 967996508 788867983 916880116 837997768 346996508 623409388 122077161
141734988 448434751 822901346 825591177 388082644 468025968 260356829 1164654 537396602 730502935 ...

output:

840988190

result:

ok single line: '840988190'

Test #12:

score: 0
Accepted
time: 64ms
memory: 699336kb

input:

15
792312195 195812430 401437979 703756992 502275277 612055402 556065888 470806179 556125857 640437896 240743729 861383776 500299988 911972088 161499505
167335533 694282920 379241393 144223073 973249939 83979787 962250505 359871412 130233016 655843497 928153117 542969567 974346871 369758881 962874102

output:

617169726

result:

ok single line: '617169726'

Test #13:

score: 0
Accepted
time: 28ms
memory: 700196kb

input:

20
1 1 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 1 2 1
2 2 1 2 2 2 1 1 1 1 1 2 2 2 2 1 1 2 1 2

output:

8388630

result:

ok single line: '8388630'

Test #14:

score: 0
Accepted
time: 48ms
memory: 699484kb

input:

15
2 1 1 2 1 2 2 1 2 1 2 1 2 2 1
1 2 2 1 2 1 1 2 1 2 1 2 1 1 2

output:

180241

result:

ok single line: '180241'

Test #15:

score: 0
Accepted
time: 36ms
memory: 700096kb

input:

20
10 3 8 2 5 7 8 3 3 10 5 6 1 2 1 9 10 2 7 10
6 6 2 3 6 10 4 6 7 2 3 3 5 7 2 8 2 1 5 1

output:

78020608

result:

ok single line: '78020608'

Test #16:

score: 0
Accepted
time: 52ms
memory: 700052kb

input:

20
999999992 999999995 999999995 999999998 999999994 999999996 999999992 1000000000 1000000000 999999997 999999999 999999994 999999998 999999992 999999999 1000000000 999999993 999999999 999999996 999999998
999999998 999999998 999999996 999999993 999999996 999999997 1000000000 999999995 999999994 999...

output:

44474368

result:

ok single line: '44474368'

Test #17:

score: 0
Accepted
time: 56ms
memory: 699892kb

input:

20
999999996 10 6 5 4 1 7 9 5 10 1 4 6 3 10 5 3 10 4 999999997
999999997 4 10 7 5 6 2 2 2 7 2 7 3 5 7 1 8 9 2 1000000000

output:

701155847

result:

ok single line: '701155847'

Test #18:

score: 0
Accepted
time: 43ms
memory: 700772kb

input:

11
1 4 2 1 10 6 3 10 1 10 10
6 8 8 7 1 1 1 9 7 9 3

output:

56064

result:

ok single line: '56064'

Test #19:

score: 0
Accepted
time: 44ms
memory: 700504kb

input:

13
999999992 999999993 999999999 999999998 999999994 999999998 999999991 999999991 999999999 999999996 999999994 999999991 999999994
999999994 999999991 999999994 999999997 999999997 1000000000 999999996 999999993 999999992 999999992 999999992 999999998 999999991

output:

184256

result:

ok single line: '184256'

Test #20:

score: 0
Accepted
time: 51ms
memory: 700824kb

input:

17
1000000000 6 4 10 10 4 2 4 10 2 7 1 3 8 4 1 999999996
999999997 3 6 4 3 6 5 10 5 7 6 10 10 7 10 3 999999997

output:

968149511

result:

ok single line: '968149511'

Test #21:

score: 0
Accepted
time: 64ms
memory: 700200kb

input:

20
5 900000001 800000002 700000003 600000004 500000005 10 5 1 100000009 10 3 2 300000007 8 500000005 3 3 800000002 2
1000000000 3 6 6 10 4 400000006 300000007 200000008 1 1 100000009 200000008 5 400000006 4 600000004 700000003 2 900000001

output:

681216662

result:

ok single line: '681216662'

Test #22:

score: 0
Accepted
time: 35ms
memory: 700828kb

input:

19
1000000000 2 777777778 7 555555556 444444445 333333334 222222223 6 4 111111112 222222223 8 444444445 555555556 6 10 888888889 1000000000
3 888888889 3 666666667 6 8 7 10 111111112 1 5 4 333333334 3 4 666666667 777777778 7 4

output:

608096464

result:

ok single line: '608096464'

Subtask #2:

score: 17
Accepted

Test #23:

score: 17
Accepted
time: 60ms
memory: 699584kb

input:

100
948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...

output:

164439470

result:

ok single line: '164439470'

Test #24:

score: 0
Accepted
time: 60ms
memory: 699300kb

input:

99
426 562 392 187 480 118 86 459 941 159 104 108 323 616 104 679 464 929 60 387 335 298 540 352 520 152 76 233 69 50 422 839 236 113 79 782 44 253 791 857 393 767 297 267 23 523 274 514 489 58 217 361 408 753 990 491 787 529 759 351 668 348 811 737 764 672 471 115 815 701 604 348 708 512 227 707 20...

output:

295469554

result:

ok single line: '295469554'

Test #25:

score: 0
Accepted
time: 55ms
memory: 700120kb

input:

100
2 1 1 2 2 2 2 1 2 2 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 1 1 2 1 2 2 1 2 2 2 1 1 1 1 2 2 2 2 2 2 2 1 2 1 1 1 1 2 2 2 2 2 2 1 2 1 2 1 2 2 1 1 2 2 1 1 2 1 2 2 2 1 1 1 1 1 1 2 2 1 2 1 1 2 1 1 1 2 1 1 2 2 1
1 2 2 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 2 1 1 1 1 1 1 1 ...

output:

865821460

result:

ok single line: '865821460'

Test #26:

score: 0
Accepted
time: 60ms
memory: 700836kb

input:

97
2 1 2 1 1 1 2 2 2 1 2 1 2 1 2 2 1 1 2 1 1 1 1 2 2 2 1 1 1 2 1 2 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 2 2 1 2 2 1 1 1 2 1 2 2 2 2 2 1 2 1 1 2 1 1 2 2 2 2 1 2 2 1 1 1 1 2 1 2 2 2 1 1 2 2 1 1 2 2 1 2 2
1 2 1 2 2 2 1 1 1 2 1 2 1 2 1 1 2 2 1 2 2 2 2 1 1 1 2 2 2 1 2 1 1 1 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 1...

output:

237658155

result:

ok single line: '237658155'

Test #27:

score: 0
Accepted
time: 39ms
memory: 700284kb

input:

100
2 7 7 7 10 10 5 3 8 7 4 4 3 3 9 9 3 4 10 10 2 2 8 6 8 5 8 5 6 5 9 7 9 4 9 4 2 6 4 7 8 8 1 4 2 4 5 3 6 8 2 5 6 1 4 10 10 1 8 7 4 9 2 8 9 5 7 8 9 8 3 5 4 7 6 3 3 1 9 4 1 4 9 1 10 3 3 9 10 7 7 8 5 8 4 10 8 4 1 4
6 8 5 8 9 2 9 9 7 3 10 1 4 10 7 1 4 1 6 8 5 7 7 7 9 3 2 3 1 9 7 2 6 5 7 9 10 1 8 1 2 6 ...

output:

12245240

result:

ok single line: '12245240'

Test #28:

score: 0
Accepted
time: 51ms
memory: 700064kb

input:

100
996 996 998 996 997 996 995 998 991 996 997 1000 992 1000 995 999 1000 999 998 992 995 998 994 996 994 994 995 1000 992 992 1000 994 993 999 997 997 997 1000 991 994 995 999 1000 999 994 992 997 992 999 992 992 1000 999 996 995 992 999 993 997 993 992 997 991 992 992 995 992 994 998 1000 998 100...

output:

699955927

result:

ok single line: '699955927'

Test #29:

score: 0
Accepted
time: 28ms
memory: 699184kb

input:

100
991 6 5 1 8 3 10 10 7 2 8 10 4 9 6 8 1 2 9 6 7 8 8 1 9 5 8 2 5 2 6 1 8 9 9 1 5 9 2 7 8 6 10 8 1 10 3 4 5 5 5 1 1 4 5 7 7 7 3 7 8 4 7 4 4 10 3 1 4 7 7 6 4 3 3 4 4 1 4 9 3 7 9 5 4 3 3 5 7 7 8 10 3 6 4 10 4 5 3 991
994 1 8 5 1 5 7 3 3 4 3 1 6 2 1 4 10 5 8 8 5 7 9 6 4 2 9 3 2 4 3 8 7 1 4 7 9 7 1 4 7...

output:

823274616

result:

ok single line: '823274616'

Test #30:

score: 0
Accepted
time: 51ms
memory: 699440kb

input:

95
3 1 9 8 2 3 7 1 9 9 10 1 1 10 10 9 9 2 4 9 6 7 10 2 8 8 2 4 7 4 9 4 2 10 1 6 1 8 9 5 2 4 1 9 3 1 10 4 10 4 3 7 1 7 9 2 10 2 5 5 4 8 4 7 8 8 2 7 3 3 9 3 9 10 5 3 2 7 10 3 10 9 1 1 1 9 7 10 2 6 5 7 10 7 10
5 7 4 3 9 9 9 4 10 1 6 5 7 6 9 3 10 3 3 3 9 2 5 5 10 10 7 8 2 7 5 5 6 6 6 10 5 6 5 6 4 10 2 8...

output:

39455183

result:

ok single line: '39455183'

Test #31:

score: 0
Accepted
time: 35ms
memory: 699320kb

input:

99
991 1000 999 997 991 997 991 998 993 993 991 997 998 998 993 991 995 999 1000 995 994 991 994 998 1000 995 997 995 996 998 997 994 997 997 993 993 999 993 998 997 998 994 998 999 998 992 991 996 1000 1000 995 994 997 997 1000 995 993 996 994 993 996 997 991 991 993 992 996 1000 994 1000 993 998 9...

output:

177632228

result:

ok single line: '177632228'

Test #32:

score: 0
Accepted
time: 40ms
memory: 699036kb

input:

93
998 9 4 6 6 3 7 6 6 2 3 1 1 4 3 4 3 10 1 7 6 6 7 2 1 6 2 7 5 10 10 5 3 6 9 3 7 8 2 4 2 5 8 4 9 8 9 6 6 10 9 8 5 9 6 7 8 6 10 4 3 4 2 10 3 6 6 3 3 7 1 5 8 8 2 4 3 6 5 4 4 9 2 4 4 10 10 5 3 4 6 5 998
991 3 7 1 2 7 4 4 7 4 8 3 7 7 6 6 1 8 3 8 2 4 9 7 2 1 6 8 4 6 1 9 6 2 8 8 5 1 5 1 6 1 2 8 1 7 7 10 ...

output:

19480584

result:

ok single line: '19480584'

Test #33:

score: 0
Accepted
time: 55ms
memory: 700200kb

input:

100
8 4 962 943 7 905 886 867 848 4 810 9 772 1 10 9 8 677 658 639 2 601 6 563 544 1 506 487 3 5 3 1 392 5 354 335 316 297 10 259 240 221 5 183 164 10 126 10 9 9 50 69 88 3 126 145 164 1 202 6 8 9 8 1 316 335 354 6 3 411 5 9 468 487 506 10 544 2 582 601 620 6 658 677 8 715 8 2 4 2 7 4 7 2 886 905 9 ...

output:

224554505

result:

ok single line: '224554505'

Test #34:

score: 0
Accepted
time: 32ms
memory: 699232kb

input:

97
8 980 2 940 920 900 880 8 5 820 5 2 7 740 5 700 9 8 640 4 8 8 3 540 520 500 7 460 7 420 9 380 10 3 6 300 280 7 240 220 200 180 10 140 4 3 80 60 7 60 10 1 7 140 160 5 200 4 10 2 280 1 3 10 360 5 400 7 9 1 480 7 520 8 560 9 8 620 640 5 680 700 720 6 7 780 1 9 3 4 9 8 920 940 960 7 9
1000 8 960 3 4 ...

output:

11356755

result:

ok single line: '11356755'

Subtask #3:

score: 19
Accepted

Dependency #2:

100%
Accepted

Test #35:

score: 19
Accepted
time: 111ms
memory: 701444kb

input:

10000
723 904 141 407 718 128 268 838 287 173 507 490 602 335 475 954 785 148 163 452 709 394 16 817 80 850 830 464 419 833 306 591 731 966 380 514 365 563 290 58 620 883 384 413 312 996 203 57 954 951 996 176 352 789 531 233 697 231 230 730 482 891 67 514 75 259 673 241 851 957 928 891 510 592 290 ...

output:

357364262

result:

ok single line: '357364262'

Test #36:

score: 0
Accepted
time: 83ms
memory: 700828kb

input:

9995
141 696 412 803 219 794 458 520 884 453 444 885 902 857 677 266 505 768 741 426 249 274 745 514 683 937 18 814 407 618 545 960 695 294 858 150 198 930 27 458 214 159 57 238 39 376 404 957 622 73 858 400 690 32 263 998 526 408 667 361 792 272 839 676 207 728 172 567 262 715 424 845 164 426 518 6...

output:

58777672

result:

ok single line: '58777672'

Test #37:

score: 0
Accepted
time: 59ms
memory: 700472kb

input:

10000
2 1 2 2 1 1 1 2 2 1 1 1 2 2 2 1 2 2 2 2 2 1 2 1 1 1 1 1 2 2 1 2 1 2 2 2 1 1 1 1 2 2 2 1 2 1 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 2 2 2 1 1 2 1 2 2 2 1 1 2 2 2 2 1 2 2 2 1 2 2 1 1 2 1 2 1 2 1 2 1 1 2 2 2 1 2 1 2 2 1 1 1 2 2 2 1 1 1 1 1 2 2 2 2 2 2 1 1 2 2 1 2 1 1 2 2 2 2 2 1 2 2 1 2 1 2 2 1 2 1 1 1 1 ...

output:

247779710

result:

ok single line: '247779710'

Test #38:

score: 0
Accepted
time: 108ms
memory: 700868kb

input:

9991
1 2 2 2 1 2 2 1 1 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 1 2 1 1 2 2 2 1 2 2 2 2 2 2 1 2 1 2 1 1 2 2 1 2 2 1 2 2 2 1 1 2 2 1 2 1 2 2 1 1 2 1 2 2 2 1 2 2 1 2 2 1 1 1 2 1 1 2 2 1 2 2 1 2 2 1 1 2 2 2 1 2 2 2 2 2 2 1 2 1 2 1 1 2 2 2 2 1 1 1 1 1 2 2 1 1 1 2 1 2 2 2 2 1 2 1 2 2 1 1 1 2 1 1 2 2 2...

output:

284526629

result:

ok single line: '284526629'

Test #39:

score: 0
Accepted
time: 91ms
memory: 700616kb

input:

10000
10 4 7 9 9 3 10 10 3 6 1 4 4 2 6 6 10 3 4 5 5 2 9 9 2 5 10 6 6 5 8 8 6 2 9 4 9 1 9 9 1 4 2 1 4 8 9 6 1 9 6 5 5 4 8 7 8 3 9 7 7 4 10 5 4 8 7 5 5 6 5 3 6 4 8 1 6 8 6 4 5 6 10 7 2 8 1 2 2 4 10 9 4 5 10 4 5 9 4 5 10 7 1 9 6 7 1 5 6 3 6 1 6 8 3 2 8 2 9 10 10 8 9 1 6 1 6 6 5 3 5 10 3 7 4 1 5 10 7 9 ...

output:

30198386

result:

ok single line: '30198386'

Test #40:

score: 0
Accepted
time: 71ms
memory: 700992kb

input:

10000
1000 998 997 995 995 998 995 994 994 998 1000 997 991 996 996 999 1000 998 991 1000 999 997 996 996 999 1000 994 993 999 994 997 994 1000 996 994 998 1000 997 992 999 1000 991 992 1000 1000 996 994 999 991 994 999 994 993 996 991 997 1000 1000 993 998 1000 998 995 993 997 992 999 998 995 992 9...

output:

592005476

result:

ok single line: '592005476'

Test #41:

score: 0
Accepted
time: 76ms
memory: 699568kb

input:

10000
995 5 2 5 9 6 10 10 3 1 9 2 4 4 5 6 6 8 4 2 9 7 5 2 2 2 8 8 1 2 10 7 6 2 10 1 6 1 6 10 5 4 7 7 8 10 10 9 4 10 8 10 6 7 7 7 1 7 3 7 9 1 9 5 5 4 8 9 5 3 4 1 7 2 7 4 8 8 1 10 4 7 8 6 6 6 10 7 3 2 4 4 10 5 4 5 2 10 4 7 10 2 10 2 9 7 2 10 9 3 6 4 5 5 2 6 5 7 7 9 3 4 2 10 3 3 1 7 8 7 2 2 2 9 6 1 9 2...

output:

782664420

result:

ok single line: '782664420'

Test #42:

score: 0
Accepted
time: 76ms
memory: 700988kb

input:

9995
9 6 6 8 7 9 6 6 1 10 5 8 6 8 10 7 9 1 5 6 4 4 9 9 8 9 2 10 8 6 6 2 8 3 7 2 7 10 3 10 1 2 5 9 4 5 9 6 1 5 7 4 10 3 9 7 4 9 3 8 3 5 3 6 5 4 1 10 10 6 7 9 4 4 10 3 8 7 9 3 9 5 2 1 7 4 9 1 8 5 7 7 6 9 4 8 2 9 8 7 6 1 3 1 8 6 3 7 1 8 1 4 6 1 6 5 7 10 2 5 2 2 2 9 2 9 9 1 4 8 8 5 9 6 6 4 8 9 7 2 7 9 4...

output:

111454521

result:

ok single line: '111454521'

Test #43:

score: 0
Accepted
time: 92ms
memory: 700676kb

input:

9995
997 998 996 993 991 991 995 998 997 991 994 993 999 998 993 999 999 999 1000 996 994 997 995 995 993 995 997 998 997 995 994 997 992 996 999 995 992 992 992 998 997 995 999 991 997 994 991 993 998 1000 998 998 991 997 996 996 993 993 998 997 993 993 999 1000 999 993 992 1000 995 993 995 995 999...

output:

2654488

result:

ok single line: '2654488'

Test #44:

score: 0
Accepted
time: 64ms
memory: 699992kb

input:

9995
993 1 1 10 5 8 9 5 8 10 4 1 3 4 8 7 2 2 1 2 7 9 7 5 8 3 3 9 7 1 9 8 6 5 2 4 9 2 1 2 9 8 1 8 6 5 3 3 3 6 1 1 9 8 3 3 4 10 5 6 7 3 1 8 4 9 7 8 4 6 5 6 3 3 4 2 1 3 6 7 5 4 4 4 6 7 8 10 3 5 3 5 3 2 4 7 9 5 6 1 1 5 3 5 7 1 7 10 8 9 1 2 10 6 3 7 10 4 3 9 1 7 2 7 10 6 6 6 9 3 10 2 8 6 2 2 9 3 2 2 8 9 ...

output:

821273565

result:

ok single line: '821273565'

Test #45:

score: 0
Accepted
time: 91ms
memory: 701044kb

input:

10000
2 1 2 2 1 2 2 1 2 2 2 1 2 1 2 1 2 2 2 2 2 1 2 1 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 1 1 2 2 1 2 1 2 2 2 2 1 2 2 2 2 1 2 1 1 2 2 2 2 2 2 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 2 2 1 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 1 1 1 2 1 1 2 1 1 2 1 2 2 2 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 2 2 ...

output:

247779710

result:

ok single line: '247779710'

Test #46:

score: 0
Accepted
time: 76ms
memory: 700012kb

input:

9997
2 2 1 1 1 1 1 2 2 2 2 2 2 2 2 2 1 2 1 2 2 2 2 2 1 2 2 1 2 1 2 2 2 2 2 1 2 2 2 1 2 1 2 2 2 1 1 2 1 2 1 1 1 2 1 2 2 2 2 2 1 1 1 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 1 2 1 2 2 1 1 2 1 2 1 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 1 2 2 1 1 1 1 1 1 2 2 2 2 2 1 1 2 2 1 1 1 2 1 1 2 1 1 2 1 2 1 2 1 1 1 1 2 1 2 1 1 2 2...

output:

423679003

result:

ok single line: '423679003'

Test #47:

score: 0
Accepted
time: 88ms
memory: 700412kb

input:

10000
1 6 9 4 6 6 7 8 3 2 8 7 9 5 1 7 5 5 7 3 4 6 5 2 9 5 3 8 7 9 5 8 5 9 2 7 6 1 10 1 8 4 1 7 6 1 4 3 6 3 8 9 8 5 10 2 7 3 2 6 6 1 10 5 7 3 4 5 10 8 2 2 5 9 4 6 8 3 9 4 3 2 7 7 7 1 2 7 6 8 3 2 5 9 5 2 2 8 3 5 6 1 7 10 10 2 2 6 3 1 2 5 9 4 10 5 3 4 10 3 10 7 1 9 8 7 10 3 2 4 9 2 1 1 7 5 2 10 6 3 8 3...

output:

199950642

result:

ok single line: '199950642'

Test #48:

score: 0
Accepted
time: 91ms
memory: 701100kb

input:

9991
9 1 3 5 3 6 9 2 1 4 9 8 1 7 8 10 4 9 8 6 4 9 2 2 1 4 10 8 1 3 9 9 8 4 6 7 1 5 4 3 6 10 9 1 8 8 10 3 10 5 10 4 9 1 2 1 7 5 7 7 3 8 10 10 3 2 10 9 3 1 6 3 1 3 2 9 3 6 4 1 7 3 6 10 2 8 6 9 4 5 8 1 3 2 4 4 8 9 4 2 10 7 5 7 5 6 3 2 9 2 4 2 4 7 7 7 5 8 4 8 5 1 4 5 5 7 10 6 4 7 4 9 5 4 8 5 2 3 7 2 3 4...

output:

776507969

result:

ok single line: '776507969'

Subtask #4:

score: 14
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #49:

score: 14
Accepted
time: 135ms
memory: 699936kb

input:

10000
178819449 858115148 715551943 171606446 213761317 988359665 576063256 256095781 409149042 902293162 594719201 256941721 563213077 739121369 747023784 395603773 775829036 453161500 254463396 842548271 626374461 725473924 962907049 719295645 379265839 989113870 123473777 864773067 481692865 6887...

output:

201814665

result:

ok single line: '201814665'

Test #50:

score: 0
Accepted
time: 96ms
memory: 700472kb

input:

9995
496766396 848601639 212437534 816213051 682051356 206603915 598487087 456225689 499883037 755936367 873541836 922958476 609128972 641821162 580040932 166549990 594503264 385739837 121868796 709521641 670526798 944122241 56727865 588343986 330945624 101972159 455841220 495575403 910967369 627576...

output:

193172022

result:

ok single line: '193172022'

Test #51:

score: 0
Accepted
time: 88ms
memory: 700128kb

input:

10000
999999996 1000000000 999999998 1000000000 999999996 999999993 999999993 999999995 999999997 999999996 999999993 999999991 999999993 999999996 999999993 999999992 999999999 999999997 999999994 1000000000 999999995 999999993 999999999 1000000000 999999999 999999992 999999991 999999994 999999995 ...

output:

187569908

result:

ok single line: '187569908'

Test #52:

score: 0
Accepted
time: 95ms
memory: 701084kb

input:

10000
999999995 2 6 4 2 3 8 2 6 4 7 3 1 2 5 1 10 10 8 4 8 1 2 6 7 4 10 1 8 2 2 5 8 2 5 10 2 1 9 10 3 7 9 6 2 6 8 7 4 6 6 8 8 5 5 8 4 1 4 7 5 8 5 5 2 3 3 5 8 2 8 4 4 9 10 9 9 2 7 1 6 3 9 9 6 6 5 5 5 1 8 10 10 9 10 4 4 1 4 7 2 3 8 2 3 8 5 1 7 1 6 5 4 3 9 3 5 4 3 5 5 5 4 9 9 2 5 6 2 10 3 3 7 5 4 6 5 10...

output:

954880607

result:

ok single line: '954880607'

Test #53:

score: 0
Accepted
time: 87ms
memory: 699496kb

input:

9991
999999997 999999992 999999992 999999999 999999992 999999991 999999999 999999993 999999993 999999994 999999996 999999996 999999999 999999997 999999995 999999995 999999991 999999991 999999992 999999997 1000000000 999999991 999999999 1000000000 999999998 999999992 1000000000 999999998 999999991 99...

output:

546883564

result:

ok single line: '546883564'

Test #54:

score: 0
Accepted
time: 91ms
memory: 699968kb

input:

9997
999999992 1 4 7 10 5 6 4 10 2 2 7 7 1 6 9 3 9 9 10 7 6 5 2 3 6 1 8 4 5 9 3 8 4 7 3 5 6 1 8 9 4 1 3 7 9 8 4 7 4 5 5 10 8 8 8 2 9 7 9 2 4 4 10 5 9 10 9 5 4 9 4 3 10 7 10 4 2 1 10 6 6 8 7 6 3 9 1 6 3 9 1 6 6 8 9 3 3 10 7 7 9 8 4 1 7 10 7 7 4 5 10 8 9 6 5 4 6 3 7 5 10 7 10 6 9 1 5 10 7 6 2 10 5 9 2...

output:

26618624

result:

ok single line: '26618624'

Test #55:

score: 0
Accepted
time: 92ms
memory: 699568kb

input:

10000
1000000000 10 999600002 9 9 999000005 8 998600007 6 998200009 998000010 5 1 10 997200014 5 996800016 10 7 2 996000020 995800021 995600022 995400023 995200024 5 994800026 994600027 994400028 994200029 994000030 993800031 3 7 993200034 993000035 2 6 2 992200039 6 991800041 6 5 991200044 9 990800...

output:

774307060

result:

ok single line: '774307060'

Test #56:

score: 0
Accepted
time: 87ms
memory: 700552kb

input:

9995
1000000000 3 9 999399640 999199520 3 998799280 8 998399040 7 8 4 2 997398440 997198320 6 996798080 996597960 8 996197720 1 5 7 995397240 995197120 10 994796880 4 2 1 8 10 993596160 993396040 993195920 992995800 4 6 992395440 992195320 5 991795080 2 991394840 9 2 9 990594360 6 4 3 989793880 9895...

output:

778878656

result:

ok single line: '778878656'

Subtask #5:

score: 12
Accepted

Test #57:

score: 12
Accepted
time: 1685ms
memory: 710980kb

input:

500000
1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...

output:

869044223

result:

ok single line: '869044223'

Test #58:

score: 0
Accepted
time: 1687ms
memory: 711088kb

input:

499993
1 1 2 1 1 2 1 1 2 1 1 1 2 2 2 2 1 1 1 2 1 1 1 2 2 2 1 1 2 2 1 2 1 2 1 2 1 2 2 2 2 1 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 1 1 2 1 1 2 1 1 1 1 2 1 1 1 2 2 1 1 2 1 1 1 2 2 2 2 1 1 2 1 2 1 2 2 1 2 1 1 1 1 2 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 2 1 1 1...

output:

480826834

result:

ok single line: '480826834'

Test #59:

score: 0
Accepted
time: 1677ms
memory: 711312kb

input:

500000
2 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 1 2 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 2 1 1 1 2 2 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 2 1 2 1 2 2 2 1 2 1 1 2 1 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 2 2 1 1 1 2 1 2 2 2 1 1 1 2 2...

output:

869044223

result:

ok single line: '869044223'

Test #60:

score: 0
Accepted
time: 1657ms
memory: 710992kb

input:

499999
2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 1 1 2 2 2 1 1 1 2 2 2 2 2 1 2 2 1 1 2 2 2 2 1 1 2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 1 2 1 1 2 1 2 1 1 2 1 1 1 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1...

output:

192864306

result:

ok single line: '192864306'

Subtask #6:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #61:

score: 0
Time Limit Exceeded

input:

500000
478857808 120748052 152370224 521089376 727355384 911252194 265312572 519248845 415507451 692560662 125645957 990108955 394317834 190949822 371963611 290037506 713376390 530982358 690217712 133395118 489663129 491260210 279563924 339997295 393985589 55775530 856283358 840587755 311099760 9180...

output:


result: