QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#167381#6626. Real Mountainscy199925 ✓1141ms74116kbC++144.3kb2023-09-07 14:11:562023-09-07 14:11:57

Judging History

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

  • [2023-09-07 14:11:57]
  • 评测
  • 测评结果:25
  • 用时:1141ms
  • 内存:74116kb
  • [2023-09-07 14:11:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using llf = long double;
const int mod = 1e6 + 3; // 1e9 + 7;//993244853;
const int MAXN = 1000005;
const int MAXT = 2100000;

// I don't remember the credit of modint, but it's not mine.
// I don't remember the credit of FFT, but it's probably mine.
// Polynomial library is due to adamant:
// https://github.com/cp-algorithms/cp-algorithms-aux/blob/master/src/polynomial.cpp
// To use polynomial sqrt, need to amend sqrt for modint.

struct mint {
	int val;
	mint() { val = 0; }
	mint(const lint &v) {
		val = (-mod <= v && v < mod) ? v : v % mod;
		if (val < 0)
			val += mod;
	}

	friend ostream &operator<<(ostream &os, const mint &a) { return os << a.val; }
	friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; }
	friend bool operator!=(const mint &a, const mint &b) { return !(a == b); }
	friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; }

	mint operator-() const { return mint(-val); }
	mint &operator+=(const mint &m) {
		if ((val += m.val) >= mod)
			val -= mod;
		return *this;
	}
	mint &operator-=(const mint &m) {
		if ((val -= m.val) < 0)
			val += mod;
		return *this;
	}
	mint &operator*=(const mint &m) {
		val = (lint)val * m.val % mod;
		return *this;
	}
	friend mint ipow(mint a, lint p) {
		mint ans = 1;
		for (; p; p /= 2, a *= a)
			if (p & 1)
				ans *= a;
		return ans;
	}
	mint inv() const { return ipow(*this, mod - 2); }
	mint &operator/=(const mint &m) { return (*this) *= m.inv(); }

	friend mint operator+(mint a, const mint &b) { return a += b; }
	friend mint operator-(mint a, const mint &b) { return a -= b; }
	friend mint operator*(mint a, const mint &b) { return a *= b; }
	friend mint operator/(mint a, const mint &b) { return a /= b; }
	operator int64_t() const { return val; }
};

struct seg {
	int tree[MAXT], lim;
	void init(vector<int> &a) {
		memset(tree, 0x3f, sizeof(tree));
		for (lim = 1; lim <= sz(a); lim <<= 1)
			;
		for (int i = 0; i < sz(a); i++) {
			tree[i + lim] = a[i];
		}
		for (int i = lim - 1; i; i--)
			tree[i] = min(tree[2 * i], tree[2 * i + 1]);
	}
	void upd(int x, int v) {
		x += lim;
		tree[x] = v;
		while (x > 1) {
			x >>= 1;
			tree[x] = min(tree[2 * x], tree[2 * x + 1]);
		}
	}
	int query(int s, int e) {
		s += lim;
		e += lim;
		int ret = 1e9;
		while (s < e) {
			if (s % 2 == 1)
				ret = min(ret, tree[s++]);
			if (e % 2 == 0)
				ret = min(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if (s == e)
			ret = min(ret, tree[s]);
		return ret;
	}
} seg;

struct bit {
	int tree[MAXN];
	void add(int x, int v) {
		for (int i = x + 2; i < MAXN; i += i & -i)
			tree[i] += v;
	}
	int query(int x) {
		int ret = 0;
		for (int i = x + 2; i; i -= i & -i)
			ret += tree[i];
		return ret;
	}
} bit;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	vector<pi> byval;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		byval.push_back({a[i], i});
	}
	seg.init(a);
	sort(all(byval));
	mint tot = 0;
	auto sum = [&](int l, int r) { return mint(1ll * (r - l + 1) * (r + l) / 2); };
	int l = 0, r = n;
	set<int> s;
	for (int i = 0; i < sz(byval) - 1; i++) {
		s.insert(byval[i][1]);
		seg.upd(byval[i][1], 1e9);
		bit.add(byval[i][1], 1);
		if (byval[i][0] == byval[i + 1][0])
			continue;
		int C = byval[i][0];
		int D = byval[i + 1][0];
		while (l < n && a[l] <= C)
			l++;
		while (r > l && a[r - 1] <= C)
			r--;
		if (l == r)
			break;
		auto it = s.lower_bound(l);
		if (it == s.end() || *it >= r)
			continue;

		int fp = *it;
		int gp = *--s.lower_bound(r);
		if (fp == gp) {
			tot += mint(1ll * (D - C) * (seg.query(l, fp - 1) + seg.query(fp + 1, r))) + sum(C, D - 1);
			continue;
		}
		int pcnt = bit.query(r - 1) - bit.query(l - 1);
		tot += sum(C, D - 1) * mint(pcnt);
		tot += sum(C + 1, D) * mint(2 * pcnt - 2);
		tot += mint(1ll * seg.query(l, fp - 1) * (D - C));
		tot += mint(1ll * seg.query(gp + 1, r - 1) * (D - C));
		tot += mint(1ll * (D - C) * min(seg.query(fp + 1, r - 1), seg.query(l, gp - 1))) - sum(C + 1, D);
	}
	cout << tot << "\n";
}

详细

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 3ms
memory: 14564kb

input:

3
29 9 9

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 0
Accepted
time: 1ms
memory: 14068kb

input:

3
62 20 71

output:

7287

result:

ok 1 number(s): "7287"

Test #3:

score: 0
Accepted
time: 1ms
memory: 14676kb

input:

10
72 33 22 22 13 49 53 57 72 85

output:

40403

result:

ok 1 number(s): "40403"

Test #4:

score: 0
Accepted
time: 5ms
memory: 14812kb

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 97 97 97 97 9...

output:

481053

result:

ok 1 number(s): "481053"

Test #5:

score: 0
Accepted
time: 1ms
memory: 15392kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

5000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

12595

result:

ok 1 number(s): "12595"

Test #7:

score: 0
Accepted
time: 0ms
memory: 14544kb

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

299

result:

ok 1 number(s): "299"

Test #8:

score: 0
Accepted
time: 5ms
memory: 15580kb

input:

5000
100 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:

224232

result:

ok 1 number(s): "224232"

Test #9:

score: 0
Accepted
time: 1ms
memory: 14588kb

input:

5000
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 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4...

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 9...

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 5ms
memory: 14928kb

input:

5000
100 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 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4...

output:

499735

result:

ok 1 number(s): "499735"

Test #12:

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

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 9...

output:

461407

result:

ok 1 number(s): "461407"

Subtask #2:

score: 3
Accepted

Dependency #1:

100%
Accepted

Test #13:

score: 3
Accepted
time: 1ms
memory: 14928kb

input:

5000
37 39 93 78 85 71 59 21 57 96 61 59 23 16 57 90 13 59 85 70 62 67 78 97 16 60 8 48 28 53 4 24 1 97 97 98 57 87 96 91 74 54 100 76 86 86 46 39 100 57 70 76 73 55 84 93 64 6 84 39 75 94 30 15 3 31 11 34 27 10 6 81 30 76 60 9 4 47 1 88 17 71 61 30 19 10 4 57 79 37 22 74 84 8 91 58 15 45 7 98 32 46...

output:

216624

result:

ok 1 number(s): "216624"

Test #14:

score: 0
Accepted
time: 1ms
memory: 14048kb

input:

29
29 62 90 18 57 29 75 67 93 45 53 45 30 77 3 52 16 31 56 37 47 52 3 23 61 66 50 39 30

output:

110566

result:

ok 1 number(s): "110566"

Test #15:

score: 0
Accepted
time: 3ms
memory: 14056kb

input:

85
11 35 37 67 43 49 100 8 72 74 42 71 14 30 69 35 42 14 67 59 48 84 15 12 64 48 34 62 78 52 95 99 58 49 63 28 84 35 17 69 97 45 40 2 52 43 56 76 82 26 4 88 59 72 99 29 62 17 42 89 25 59 48 36 31 63 3 85 16 89 41 23 24 60 79 29 32 72 21 82 64 54 47 85 95

output:

729618

result:

ok 1 number(s): "729618"

Test #16:

score: 0
Accepted
time: 1ms
memory: 15276kb

input:

5000
13 76 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9 4 8 14 31 91 97 72 23 73 68 70 51 78 2 19 10 38 11 16 19 64 97 47 43 65 28 88 63 50 49 23 28 37 20 68 100 21 65 37 64 96 38 40 44 100 11 62 1 16 8 57 44 87 3 86 4 73 96 56 16 77 32 52 98 27 14 7 85 28 97 19 24 5 3 26 41 56 91 25 63 55 69...

output:

959697

result:

ok 1 number(s): "959697"

Test #17:

score: 0
Accepted
time: 1ms
memory: 15028kb

input:

5000
85 23 93 33 88 25 22 89 72 56 41 51 15 91 3 20 50 67 25 64 51 22 5 60 34 88 51 62 65 1 48 73 91 65 19 2 8 33 75 12 72 87 62 89 76 45 77 23 32 82 97 76 52 3 72 66 38 40 82 60 89 21 5 70 69 58 77 81 17 70 100 61 72 92 19 74 13 13 7 8 22 79 26 74 85 46 35 42 78 74 85 7 94 34 17 42 40 40 91 46 78 9...

output:

136364

result:

ok 1 number(s): "136364"

Test #18:

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

input:

5000
57 6 44 49 8 49 13 57 78 49 39 20 52 16 8 39 46 96 23 32 21 26 50 60 41 23 49 73 87 46 34 1 36 96 75 81 64 70 83 55 88 6 45 17 8 27 11 15 46 73 29 29 6 82 96 82 96 39 27 14 49 55 21 69 13 43 60 63 38 4 56 22 84 37 38 10 32 83 46 56 70 11 78 55 10 3 92 18 34 68 12 37 62 13 63 75 82 96 93 45 12 3...

output:

171486

result:

ok 1 number(s): "171486"

Test #19:

score: 0
Accepted
time: 5ms
memory: 15344kb

input:

5000
37 53 87 68 55 84 34 69 19 67 99 81 62 75 81 30 31 34 4 91 68 36 33 77 80 11 28 13 66 76 7 26 40 63 62 77 30 95 45 48 87 92 60 62 12 51 4 71 32 6 7 77 24 49 3 48 5 18 72 10 37 46 86 92 82 78 75 39 47 70 3 39 69 29 63 76 76 96 1 44 23 54 47 31 67 35 20 71 84 54 74 24 51 57 54 85 74 48 51 21 39 5...

output:

276173

result:

ok 1 number(s): "276173"

Test #20:

score: 0
Accepted
time: 1ms
memory: 14000kb

input:

5000
96 9 3 8 5 1 9 1 7 6 1 9 3 6 7 10 3 9 5 10 2 7 8 7 6 10 8 8 8 3 4 4 1 7 7 8 7 7 6 1 4 4 10 6 6 6 6 9 10 7 10 6 3 5 4 3 4 6 4 9 5 4 10 5 3 1 1 4 7 10 6 1 10 6 10 9 4 7 1 8 7 1 1 10 9 10 4 7 9 7 2 4 4 8 1 8 5 5 7 8 2 6 7 7 9 7 5 6 6 6 3 9 7 4 4 8 2 5 2 8 6 7 10 3 1 7 1 7 2 6 10 8 7 3 5 3 4 10 8 2...

output:

190251

result:

ok 1 number(s): "190251"

Test #21:

score: 0
Accepted
time: 5ms
memory: 15064kb

input:

5000
98 6 6 5 10 8 3 7 1 3 4 10 6 4 4 7 3 9 3 9 4 8 4 1 1 7 2 3 3 8 10 1 8 2 9 10 8 1 6 9 4 7 7 3 5 8 8 3 10 9 3 8 7 10 8 10 1 5 7 4 6 8 10 4 10 1 2 1 6 8 7 4 7 3 6 4 3 6 6 6 7 2 2 8 7 4 7 5 8 7 9 4 5 3 6 1 6 1 5 3 5 9 5 2 5 5 9 7 4 3 7 6 1 8 2 3 9 8 6 3 10 9 7 7 3 2 2 10 5 5 8 6 8 6 8 7 8 9 8 10 1 ...

output:

491746

result:

ok 1 number(s): "491746"

Test #22:

score: 0
Accepted
time: 1ms
memory: 14432kb

input:

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

output:

47458

result:

ok 1 number(s): "47458"

Test #23:

score: 0
Accepted
time: 5ms
memory: 14748kb

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 97 97 97 97 97 97 97 97 97 97 97 97 ...

output:

410269

result:

ok 1 number(s): "410269"

Test #24:

score: 0
Accepted
time: 1ms
memory: 15228kb

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 9...

output:

89583

result:

ok 1 number(s): "89583"

Test #25:

score: 0
Accepted
time: 0ms
memory: 14120kb

input:

5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 96 96 96 96...

output:

403710

result:

ok 1 number(s): "403710"

Test #26:

score: 0
Accepted
time: 5ms
memory: 14612kb

input:

5000
1 1 51 1 1 1 65 1 1 21 1 1 20 1 1 1 13 1 1 1 1 2 2 2 68 2 2 2 2 2 2 2 2 2 2 2 2 2 2 8 2 43 2 2 2 2 2 2 3 3 60 3 3 3 3 63 16 3 3 3 50 59 3 3 16 75 3 6 3 3 3 3 4 10 4 85 4 4 4 46 4 70 43 4 4 4 4 4 4 4 4 4 61 4 4 4 4 5 5 5 5 5 5 5 5 5 5 57 5 5 5 8 5 5 5 5 5 5 5 5 3 6 6 6 49 6 25 6 6 6 21 6 6 6 6 6...

output:

287987

result:

ok 1 number(s): "287987"

Test #27:

score: 0
Accepted
time: 5ms
memory: 14540kb

input:

5000
1 1 3 1 1 1 1 1 61 1 1 1 1 12 1 1 24 96 1 60 1 1 1 37 1 1 1 1 2 2 2 2 42 2 2 2 2 2 2 2 2 46 69 2 2 39 3 3 3 3 3 1 3 27 3 3 3 3 3 3 3 3 3 3 43 3 3 3 3 3 3 29 3 3 57 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 12 75 4 24 4 4 89 4 4 4 24 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 37 5 5 5 5 5 5 5 41 5 5 6 6 6 6 6 ...

output:

482347

result:

ok 1 number(s): "482347"

Test #28:

score: 0
Accepted
time: 5ms
memory: 14140kb

input:

5000
1 1 85 51 96 1 1 82 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 13 2 48 2 2 2 2 2 92 8 2 2 78 2 3 69 3 20 3 3 3 3 3 3 3 3 3 3 3 70 3 3 3 62 3 26 3 4 4 33 4 4 4 4 4 4 26 4 84 4 85 4 4 4 4 32 5 100 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 75 5 5 5 5 5 89 5 5 5 22 5 5 5 5 6 6 6 6 6 6 60 19 6 6 55 6 100 6 6 6 6 6...

output:

714189

result:

ok 1 number(s): "714189"

Test #29:

score: 0
Accepted
time: 3ms
memory: 13864kb

input:

3
100 1 100

output:

24750

result:

ok 1 number(s): "24750"

Test #30:

score: 0
Accepted
time: 3ms
memory: 14448kb

input:

3
1 2 3

output:

0

result:

ok 1 number(s): "0"

Test #31:

score: 0
Accepted
time: 0ms
memory: 14012kb

input:

3
3 2 1

output:

0

result:

ok 1 number(s): "0"

Test #32:

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

input:

3
100 100 100

output:

0

result:

ok 1 number(s): "0"

Test #33:

score: 0
Accepted
time: 3ms
memory: 13672kb

input:

5
100 1 2 1 98

output:

57420

result:

ok 1 number(s): "57420"

Subtask #3:

score: 3
Accepted

Dependency #2:

100%
Accepted

Test #34:

score: 3
Accepted
time: 1ms
memory: 15524kb

input:

5000
407609 427494 229544 174201 237923 974106 83376 278833 559089 156614 683522 171512 683333 140787 568442 381473 161683 880608 849863 503926 181414 366081 829869 14514 752859 488252 473987 428487 879011 543082 18678 52954 281414 582364 737092 67586 693723 150612 421762 168780 815185 837639 336407...

output:

160078

result:

ok 1 number(s): "160078"

Test #35:

score: 0
Accepted
time: 2ms
memory: 14248kb

input:

5000
324185 878650 448990 287827 888670 462626 311392 94845 624934 852431 423082 644472 850538 538546 598119 933556 689768 600346 419141 239685 84961 218303 722359 140131 439002 178043 379766 746730 164699 243212 242556 766875 939123 638932 902279 505690 858993 920537 834524 411373 599085 219525 170...

output:

2068

result:

ok 1 number(s): "2068"

Test #36:

score: 0
Accepted
time: 1ms
memory: 14540kb

input:

5000
841657 391324 32430 850839 623490 685765 970388 174905 921452 331520 312372 102650 74279 920171 330824 437075 937364 657275 330938 268753 252426 895095 409005 642135 771605 977274 974068 398234 41521 33461 454937 663907 774163 856362 602136 205265 652641 578674 865633 7316 813301 675449 500505 ...

output:

708104

result:

ok 1 number(s): "708104"

Test #37:

score: 0
Accepted
time: 1ms
memory: 15076kb

input:

5000
790937 842480 994980 221361 274236 206989 974213 990917 954593 994634 19229 799802 241485 317930 103604 989158 689642 377013 932920 228704 188678 780021 525688 543560 457748 667066 879847 749181 584105 733590 744223 153637 431872 912930 608539 610665 817911 381303 278395 474101 597200 281526 55...

output:

31687

result:

ok 1 number(s): "31687"

Test #38:

score: 0
Accepted
time: 3ms
memory: 15624kb

input:

5000
41209 456309 817729 366690 97805 834807 514354 542881 789763 939885 800547 222137 674460 348846 271470 365613 689705 376583 192382 605747 636819 966458 656727 358197 432023 406203 129807 247956 245954 376305 493389 460256 169145 775931 271761 170273 354804 38824 72812 554833 469694 878973 86477...

output:

421232

result:

ok 1 number(s): "421232"

Test #39:

score: 0
Accepted
time: 5ms
memory: 15288kb

input:

5000
999998 6 4 9 8 9 3 7 8 9 9 10 2 6 8 9 6 6 3 2 1 6 10 10 1 3 9 3 7 6 4 1 6 6 5 1 4 10 3 5 8 6 5 7 8 7 1 5 6 3 9 9 6 2 6 2 6 9 7 4 9 5 1 9 3 3 10 3 8 4 6 2 4 7 8 10 2 3 6 6 10 1 8 5 10 3 2 8 4 8 2 7 2 3 3 5 2 6 3 5 2 2 6 4 8 9 9 1 1 8 4 5 2 2 4 8 8 9 8 8 1 1 10 10 2 7 7 4 9 3 5 1 4 1 6 5 5 6 5 9 ...

output:

746700

result:

ok 1 number(s): "746700"

Test #40:

score: 0
Accepted
time: 0ms
memory: 15652kb

input:

5000
999992 3 7 8 5 4 4 9 9 7 9 1 2 5 1 10 1 4 4 1 8 6 3 7 10 1 8 3 6 6 7 6 10 3 2 7 10 5 5 8 7 2 10 2 2 1 4 1 2 6 7 7 4 9 3 8 5 8 2 10 7 6 6 2 2 8 5 9 7 10 3 9 9 9 3 6 6 6 1 4 3 4 7 1 7 5 10 1 4 4 4 4 1 7 4 5 4 8 1 1 9 8 5 7 10 3 4 2 4 2 1 10 10 9 10 9 6 6 8 5 6 7 2 6 2 5 7 7 8 1 1 5 5 4 9 5 1 9 4 ...

output:

936681

result:

ok 1 number(s): "936681"

Test #41:

score: 0
Accepted
time: 1ms
memory: 14008kb

input:

5000
999998 4 4 1 3 6 6 3 9 4 2 2 3 7 2 3 3 8 3 6 4 1 9 4 9 2 7 7 1 2 8 4 4 4 2 6 3 2 2 10 5 9 7 10 8 8 4 9 8 8 6 8 4 10 8 5 3 5 9 5 1 9 1 5 10 4 6 10 8 6 10 4 5 1 3 9 8 1 6 2 5 9 1 6 6 9 2 1 7 8 4 10 2 9 8 10 7 4 3 2 3 6 6 2 9 1 5 3 2 4 7 8 5 1 10 4 3 4 1 4 10 8 2 4 5 1 7 6 5 4 6 6 6 4 8 3 3 8 5 3 ...

output:

417503

result:

ok 1 number(s): "417503"

Test #42:

score: 0
Accepted
time: 6ms
memory: 15328kb

input:

5000
999948 999574 998450 998377 997104 996783 996713 996366 995456 994594 994501 994380 994217 993968 992750 991050 990910 990573 989753 989064 988881 988318 986883 986862 986328 986008 985365 985008 984914 984865 983656 982819 982080 981045 980961 979980 979837 979513 979063 979010 978893 978871 9...

output:

387878

result:

ok 1 number(s): "387878"

Test #43:

score: 0
Accepted
time: 1ms
memory: 15828kb

input:

5000
999656 999554 999540 999479 998728 998266 998135 997445 997343 997307 996168 996075 995690 995601 995485 995039 994643 994563 994437 994409 994046 992899 992012 991904 991646 991333 991030 990882 990535 990485 990215 989589 989459 988836 988758 988361 987993 987893 986801 986616 985296 985075 9...

output:

758881

result:

ok 1 number(s): "758881"

Test #44:

score: 0
Accepted
time: 6ms
memory: 14624kb

input:

5000
999745 999681 999438 999290 998646 998539 996901 995889 995537 995286 994645 994283 994068 993724 993702 993470 992207 991680 991538 991242 990759 990456 990446 990162 990089 989932 989585 988752 987975 986845 986491 985021 984919 984404 984320 983818 983802 983535 982664 982654 982322 982198 9...

output:

815548

result:

ok 1 number(s): "815548"

Test #45:

score: 0
Accepted
time: 1ms
memory: 14164kb

input:

5000
456 656 902 1276 1750 2041 2162 2545 2764 840730 3917 4013 4043 4770 5105 6433 6570 892211 388382 8141 315769 9795 11190 11198 48460 11847 12832 12923 13208 540409 14334 14460 14791 16049 16061 833381 53517 18764 18960 18991 19248 19385 19553 20337 20544 20709 21207 21511 21635 21897 22750 2314...

output:

316760

result:

ok 1 number(s): "316760"

Test #46:

score: 0
Accepted
time: 2ms
memory: 15488kb

input:

5000
78571 587478 1151 147827 1661 45324 2424 3378 4787 4852 5082 5153 5454 5663 5821 6066 6450 6648 6721 6742 706243 8351 277257 9667 10153 10628 10666 10796 11145 11164 12384 12470 13662 14365 14661 15083 15395 15630 16735 16835 434264 17567 17935 18130 18171 18187 18792 19478 19511 144720 20558 7...

output:

464860

result:

ok 1 number(s): "464860"

Test #47:

score: 0
Accepted
time: 1ms
memory: 15448kb

input:

5000
22 525508 632396 1493 2253 2705 3796 5156 5748 5798 6126 6371 6668 7005 7679 7782 9921 10415 11155 11188 11276 11674 12071 12250 13171 13606 14445 15195 15949 16144 543082 16966 17354 18114 18208 18394 18678 19214 20762 20769 108130 22100 22126 432537 22783 292674 24220 24322 286257 25697 25843...

output:

157588

result:

ok 1 number(s): "157588"

Subtask #4:

score: 3
Accepted

Dependency #3:

100%
Accepted

Test #48:

score: 3
Accepted
time: 1ms
memory: 14960kb

input:

5000
997957785 512940168 886812983 292704508 66972744 745388734 579742371 432326189 226855608 715635702 168572812 769662393 218874369 18746605 943268443 924884992 100185087 342096321 186794364 725565698 672348879 402818680 210549218 468483814 278085462 594095994 467068289 469823095 910788538 8620764...

output:

574214

result:

ok 1 number(s): "574214"

Test #49:

score: 0
Accepted
time: 5ms
memory: 14196kb

input:

5000
402507961 495452843 922429127 169076032 460674860 142611874 640434071 716406249 7086719 599082087 387205206 812120571 824841214 595128230 248001147 392421214 688465386 870344738 229706162 704594766 381740536 592528176 780235864 328985818 611226577 417895225 756372992 277250406 82665360 95586668...

output:

140342

result:

ok 1 number(s): "140342"

Test #50:

score: 0
Accepted
time: 6ms
memory: 15412kb

input:

5000
519391833 921903998 623615869 143446555 481325606 893100393 60405191 373222261 786152563 21810609 712944766 755593532 32265316 715525989 880806632 609940593 700184960 570872988 506018544 560297821 234676788 972380398 410352546 107111435 588912720 547585017 748311474 696825545 58951048 768599517...

output:

424748

result:

ok 1 number(s): "424748"

Test #51:

score: 0
Accepted
time: 2ms
memory: 14740kb

input:

5000
758674809 792293635 255214426 70591884 274149175 671760916 245202229 402774225 153987734 868723155 440758789 335240058 700441394 794524201 837165985 692541240 105217727 588905263 271534902 847964464 526124929 687599539 105418178 67701881 506111187 423356858 32818330 583324320 984869793 74046642...

output:

459508

result:

ok 1 number(s): "459508"

Test #52:

score: 0
Accepted
time: 5ms
memory: 14732kb

input:

5000
875558681 363968983 516209681 44962406 999832625 982057947 370206054 764622941 933053578 586418973 61465646 278713019 467674008 914921960 764938766 469869131 116937301 729625000 398104180 998634815 233836989 67451762 590310669 845827497 483797330 993238137 614691405 152642563 106379672 84816655...

output:

966944

result:

ok 1 number(s): "966944"

Test #53:

score: 0
Accepted
time: 1ms
memory: 14048kb

input:

5000
999999996 10 10 7 10 6 2 5 4 1 2 2 8 6 9 6 8 6 1 5 1 3 9 1 2 3 6 10 9 2 6 5 3 2 9 10 3 7 4 3 5 5 6 1 7 4 7 9 10 1 2 1 5 2 2 6 2 10 8 9 6 8 6 7 5 8 9 6 7 8 5 8 9 9 8 1 2 4 3 4 10 9 4 3 1 9 4 10 4 1 6 7 1 4 8 9 9 7 7 7 6 6 5 9 3 5 10 10 5 9 4 3 6 2 8 3 7 2 7 4 7 2 8 10 8 1 1 8 7 8 4 1 4 10 4 6 6 ...

output:

947680

result:

ok 1 number(s): "947680"

Test #54:

score: 0
Accepted
time: 5ms
memory: 15232kb

input:

5000
999999994 4 10 9 10 5 8 5 2 10 2 10 9 1 4 5 4 5 8 3 6 5 5 5 5 4 8 4 1 1 7 7 3 2 6 5 1 4 3 6 1 9 5 1 8 10 9 7 4 6 2 10 9 4 1 9 4 1 3 2 5 7 2 6 3 8 5 8 3 2 3 2 2 4 1 5 1 9 6 3 5 6 2 7 8 7 3 2 7 4 4 5 9 2 9 8 1 10 5 4 10 4 10 8 5 9 6 3 8 9 2 5 6 7 8 2 5 5 4 6 2 1 9 3 4 10 6 4 10 2 9 2 6 4 7 1 2 9 ...

output:

755373

result:

ok 1 number(s): "755373"

Test #55:

score: 0
Accepted
time: 0ms
memory: 15460kb

input:

5000
999999999 10 10 1 6 9 3 7 3 4 9 2 5 10 4 8 2 3 10 4 8 1 8 10 8 6 7 1 5 10 3 7 2 10 9 5 1 3 5 1 10 6 6 1 9 3 10 1 10 5 8 2 4 10 5 4 8 10 8 5 4 3 9 4 8 10 10 8 4 8 8 6 7 7 6 1 1 10 9 9 7 8 6 10 3 7 9 5 6 1 10 10 8 7 9 4 1 3 1 4 9 10 5 7 2 7 9 6 2 7 5 7 7 7 10 8 6 8 5 2 6 2 7 9 9 6 10 2 1 10 6 6 8...

output:

832060

result:

ok 1 number(s): "832060"

Test #56:

score: 0
Accepted
time: 3ms
memory: 14000kb

input:

5000
999876238 999633685 998806321 998320831 997691244 996156374 994451800 994408489 993654809 993470983 993430691 993123330 992673648 992272504 991831988 991712194 991668941 990468488 990250454 990017160 989890144 989818849 989760756 989204420 989097894 988888670 988809672 988437850 988084289 98632...

output:

771530

result:

ok 1 number(s): "771530"

Test #57:

score: 0
Accepted
time: 0ms
memory: 14668kb

input:

5000
999747915 999373373 998745713 998542920 998012692 997807431 997306800 996565871 996359499 996105619 994402959 994148278 993920171 993280694 993055728 992918531 992716101 991881182 991776134 991761677 991176747 990098498 990003103 989676582 988211040 987828572 987744210 987103273 986525857 98644...

output:

738136

result:

ok 1 number(s): "738136"

Test #58:

score: 0
Accepted
time: 1ms
memory: 15240kb

input:

5000
999932866 999294885 998741858 997860230 997640328 997610665 997590107 997589301 997328881 996911431 996689954 996604231 996489748 996387653 995621774 995582285 995488890 995434960 995418373 994275128 993030681 992578823 991763295 991685471 991570664 990960610 990946458 990648782 990573285 99047...

output:

865453

result:

ok 1 number(s): "865453"

Test #59:

score: 0
Accepted
time: 1ms
memory: 14280kb

input:

5000
365722 936686 1537157 1822569 1921921 2230752 3153946 984112729 3697282 4062564 4215852 4700715 4717585 5184386 5401337 333997838 6689041 360703454 7668188 8199484 8853655 8995133 9427313 791699864 10803308 10900658 11057870 11432356 166920748 14239205 14247212 14550006 16494085 17074678 174391...

output:

225562

result:

ok 1 number(s): "225562"

Test #60:

score: 0
Accepted
time: 6ms
memory: 15020kb

input:

5000
68557 94859 733850 1330745 1480549 1594673 312154654 1925237 2248701 2716888 3062620 3362048 3406773 4284215 5171715 5439201 5617227 5921452 199692462 6167263 6222513 978621787 6892694 8102650 8239129 8421207 8431372 8640709 9344252 9482286 9692725 9842728 9880011 11223002 11511564 11675449 131...

output:

985075

result:

ok 1 number(s): "985075"

Test #61:

score: 0
Accepted
time: 1ms
memory: 14612kb

input:

5000
981215 1273134 1855626 2132318 2273667 2452472 3011697 3082546 3820005 4186548 4959436 404834171 5130874 5599429 586413126 705738318 6792847 6800432 468493620 7496049 175997558 9090898 9186193 9278688 9567790 10322933 83900620 604317351 10863794 10937786 10977643 10981136 11172926 11649639 1187...

output:

894439

result:

ok 1 number(s): "894439"

Subtask #5:

score: 4
Accepted

Dependency #2:

100%
Accepted

Test #62:

score: 4
Accepted
time: 590ms
memory: 74104kb

input:

1000000
62 1 73 90 31 17 19 13 36 87 67 10 97 21 84 61 55 9 32 55 63 32 72 52 5 76 44 40 90 40 93 77 74 83 30 64 59 36 50 72 27 24 32 10 54 91 54 35 2 23 39 33 82 60 9 22 52 59 63 71 15 18 52 62 21 81 35 40 57 85 52 60 22 51 37 43 67 93 79 50 77 94 61 31 44 73 72 36 26 86 26 23 27 93 74 52 11 93 90 ...

output:

911708

result:

ok 1 number(s): "911708"

Test #63:

score: 0
Accepted
time: 595ms
memory: 73940kb

input:

1000000
38 57 20 16 70 40 44 25 80 4 27 66 3 92 65 51 40 58 10 3 15 55 63 77 48 56 23 79 78 69 70 7 71 46 34 60 29 61 17 66 27 6 47 55 66 15 42 99 88 56 21 81 89 40 17 83 61 38 8 67 7 13 17 84 98 24 46 17 58 51 95 70 7 48 62 9 7 14 26 42 35 38 35 16 97 5 5 90 77 68 88 6 15 24 57 54 3 38 44 9 14 8 45...

output:

412956

result:

ok 1 number(s): "412956"

Test #64:

score: 0
Accepted
time: 597ms
memory: 73808kb

input:

1000000
10 90 77 45 50 63 86 89 55 51 50 97 78 92 22 99 96 21 73 41 52 96 91 15 19 93 82 54 23 88 37 26 48 51 52 73 18 74 29 98 25 53 6 27 40 62 77 23 42 48 63 28 64 9 1 90 30 5 66 91 29 44 34 29 87 12 96 88 47 49 46 29 64 79 84 3 71 67 81 74 82 7 22 83 18 9 12 29 18 24 94 44 37 19 93 36 36 92 66 70...

output:

837967

result:

ok 1 number(s): "837967"

Test #65:

score: 0
Accepted
time: 610ms
memory: 73624kb

input:

1000000
90 45 27 67 85 90 2 5 95 69 10 49 88 62 7 78 77 71 51 96 4 10 82 31 62 85 61 5 6 10 11 59 61 15 43 69 88 3 92 87 20 39 25 64 51 74 65 79 20 77 49 77 67 89 1 56 43 84 14 87 18 35 95 40 52 47 11 60 56 11 97 43 49 67 17 69 11 80 28 66 32 50 91 55 75 37 44 83 76 9 60 35 26 58 84 38 19 41 32 50 5...

output:

581326

result:

ok 1 number(s): "581326"

Test #66:

score: 0
Accepted
time: 624ms
memory: 73772kb

input:

1000000
62 20 71 79 5 22 2 61 2 65 8 31 20 80 12 100 73 88 48 68 73 13 27 35 73 23 63 4 32 67 96 79 97 45 7 48 36 41 100 34 40 58 92 92 88 60 8 71 30 72 72 30 25 67 20 68 5 75 55 42 77 69 7 51 100 40 99 46 77 45 49 7 58 9 40 18 30 58 71 15 79 73 43 36 89 98 1 50 24 4 74 61 94 29 34 71 62 88 30 61 94...

output:

414210

result:

ok 1 number(s): "414210"

Test #67:

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

input:

344
82 13 48 35 40 17 86 8 25 13 100 63 2 39 78 32 29 14 63 12 71 68 42 19 7 33 37 91 93 98 17 50 64 96 55 28 44 98 62 98 69 55 19 32 47 65 52 45 28 74 21 41 40 63 2 10 72 88 47 84 18 34 22 39 71 14 20 93 30 43 100 48 91 91 11 49 21 30 31 36 99 2 21 86 87 26 30 19 98 27 25 52 21 89 47 98 44 23 26 72...

output:

388100

result:

ok 1 number(s): "388100"

Test #68:

score: 0
Accepted
time: 1ms
memory: 14380kb

input:

338
32 39 60 38 62 15 49 53 95 46 34 74 78 3 76 69 100 42 83 55 16 48 56 97 48 15 13 78 25 59 41 48 75 26 33 15 50 20 32 73 38 40 100 79 36 22 7 19 40 7 63 76 97 64 70 54 4 70 55 75 13 40 87 10 95 93 41 60 12 30 14 42 92 58 65 76 73 29 77 82 10 84 74 50 89 40 23 31 86 18 7 92 19 37 84 77 94 44 10 5 ...

output:

60017

result:

ok 1 number(s): "60017"

Test #69:

score: 0
Accepted
time: 335ms
memory: 73864kb

input:

1000000
94 9 9 10 5 7 4 1 3 5 7 7 10 6 10 3 5 3 2 7 9 8 7 7 3 3 7 6 4 5 9 6 5 1 1 3 4 4 2 3 4 3 1 4 3 8 8 5 6 1 9 3 7 3 3 9 6 3 5 10 4 9 6 10 7 10 10 9 3 4 4 9 6 8 6 10 4 9 8 6 2 8 1 7 2 1 1 5 5 5 6 8 9 8 7 7 6 3 7 5 8 4 4 6 7 3 6 1 9 5 5 9 8 4 8 4 2 4 9 9 1 2 9 7 10 1 7 5 4 9 5 9 5 5 9 8 10 2 1 6 3...

output:

399462

result:

ok 1 number(s): "399462"

Test #70:

score: 0
Accepted
time: 342ms
memory: 73780kb

input:

1000000
92 8 3 8 4 4 1 9 8 2 2 3 9 5 3 2 7 1 4 8 9 10 8 4 2 4 9 5 8 5 3 6 8 9 8 3 10 9 10 7 3 9 10 9 4 4 1 1 2 1 9 7 2 1 3 5 5 2 10 6 9 10 7 6 4 3 10 2 4 6 10 9 7 6 6 6 7 6 1 8 8 2 7 9 1 9 9 8 1 2 2 1 8 7 8 3 10 2 1 10 3 10 3 1 3 9 5 2 3 10 8 10 6 6 4 3 7 3 8 1 7 7 3 3 10 2 6 9 6 5 3 8 7 2 3 1 7 7 1...

output:

411420

result:

ok 1 number(s): "411420"

Test #71:

score: 0
Accepted
time: 325ms
memory: 73844kb

input:

1000000
97 3 7 2 10 4 1 9 9 7 6 1 4 10 7 4 6 8 2 6 6 6 4 8 7 5 2 6 10 4 8 9 5 5 4 2 6 9 4 9 9 9 9 3 5 6 5 7 2 5 9 4 10 3 1 7 1 1 10 1 2 4 6 1 8 2 9 9 1 10 7 7 4 7 4 7 1 3 8 7 9 9 3 4 5 5 6 5 7 1 8 5 6 2 4 9 9 7 9 3 5 7 2 2 1 5 5 5 6 9 2 8 9 1 10 9 9 3 2 7 6 10 2 6 1 10 10 9 4 7 8 3 1 2 7 6 8 9 8 5 2...

output:

404981

result:

ok 1 number(s): "404981"

Test #72:

score: 0
Accepted
time: 276ms
memory: 73628kb

input:

1000000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

441999

result:

ok 1 number(s): "441999"

Test #73:

score: 0
Accepted
time: 273ms
memory: 73772kb

input:

1000000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

414038

result:

ok 1 number(s): "414038"

Test #74:

score: 0
Accepted
time: 292ms
memory: 73692kb

input:

1000000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

990184

result:

ok 1 number(s): "990184"

Test #75:

score: 0
Accepted
time: 371ms
memory: 73872kb

input:

1000000
1 1 1 1 1 1 1 1 20 1 95 1 75 1 1 1 1 1 1 1 1 1 1 1 1 1 76 1 66 1 1 1 1 1 1 1 1 1 1 46 1 1 1 1 1 1 1 36 1 1 1 1 1 60 83 1 1 1 1 1 4 1 1 89 43 79 1 1 1 1 36 1 12 55 1 1 1 1 1 58 1 1 1 1 41 1 1 1 1 1 49 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 94 1 1 1 1 10 1 1 1 1 69 1 1 1 1 1 1 1 80 1 1 1 1 ...

output:

597485

result:

ok 1 number(s): "597485"

Test #76:

score: 0
Accepted
time: 365ms
memory: 73772kb

input:

1000000
1 1 1 1 1 1 37 1 1 1 1 87 1 1 1 26 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 17 1 1 1 1 1 1 1 7 81 1 1 1 1 1 1 28 1 1 1 1 1 19 1 1 1 1 1 1 1 1 1 86 42 1 1 1 1 90 1 1 1 55 1 1 54 1 1 1 1 1 1 1 1 1 50 1 50 1 1 1 1 11 1 29 1 1 1 1 1 1 1 71 1 51 1 1 1 55 1 1 1 1 1 96 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

151444

result:

ok 1 number(s): "151444"

Test #77:

score: 0
Accepted
time: 375ms
memory: 73872kb

input:

1000000
1 1 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 50 53 1 1 1 1 1 1 1 1 1 1 30 1 1 1 1 1 1 1 1 1 1 38 1 1 1 1 1 17 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 87 98 1 52 1 1 1 1 1 89 1 1 1 1 1 1 53 1 38 1 1 38 1 1 1 1 1 4 1 1 1 1 89 1 1 1 1 1 1 1 1 1 73 1 39 1 12 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 44 1 1 1 1 11 1 7...

output:

199390

result:

ok 1 number(s): "199390"

Subtask #6:

score: 5
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #78:

score: 5
Accepted
time: 1060ms
memory: 73880kb

input:

1000000
622938 15975 918117 936610 591852 964157 497015 927573 707846 110983 718965 677491 734234 375747 495089 942379 699259 607537 285730 79728 5024 198936 298018 890552 253416 755007 824942 881151 787216 862196 599978 308613 670910 753609 224794 195340 59002 267666 864362 24923 226543 588648 7910...

output:

187155

result:

ok 1 number(s): "187155"

Test #79:

score: 0
Accepted
time: 1064ms
memory: 73800kb

input:

1000000
905914 438316 516674 81939 415420 591975 37157 479537 318825 23530 532987 324018 134505 598151 630250 318834 923514 831300 512488 680962 453166 609565 620546 480998 227691 526848 74902 412630 449065 729103 381848 615232 408184 649314 920721 530756 595895 957890 658779 138359 323230 153391 96...

output:

756174

result:

ok 1 number(s): "756174"

Test #80:

score: 0
Accepted
time: 1141ms
memory: 73820kb

input:

1000000
822490 113664 703416 452461 66167 113199 73685 295549 351965 719348 272548 764275 334414 771717 659927 870917 418896 359550 114470 640913 132522 494491 513036 606614 913834 216640 13385 955065 958945 461937 862622 104962 98596 673177 85908 160348 761165 727815 38837 572440 915641 792173 1225...

output:

257782

result:

ok 1 number(s): "257782"

Test #81:

score: 0
Accepted
time: 1079ms
memory: 73812kb

input:

1000000
339961 402146 286856 15473 800987 336338 732681 375609 839972 198436 129134 255156 301259 410239 135736 374436 666491 575263 26268 413085 556883 947091 232386 75914 246437 48574 318087 349673 868471 219481 850811 226186 900933 147504 561572 635731 330621 610145 102650 976895 354049 991200 45...

output:

397480

result:

ok 1 number(s): "397480"

Test #82:

score: 0
Accepted
time: 1068ms
memory: 74020kb

input:

1000000
223833 44790 282110 385995 675925 824858 960697 158917 873112 861550 901398 695413 725361 551102 165413 926519 418769 103513 595546 373037 493134 23505 92172 234235 932580 705662 256570 957516 378351 919611 331585 715915 558642 171367 759463 298027 495891 380070 482708 410976 913756 597278 2...

output:

455323

result:

ok 1 number(s): "455323"

Test #83:

score: 0
Accepted
time: 345ms
memory: 73864kb

input:

1000000
999999 8 9 5 6 3 1 1 3 9 6 2 6 9 2 3 10 8 4 1 8 8 6 5 10 7 4 5 8 7 6 9 8 7 4 8 6 4 3 3 7 8 6 9 8 9 3 3 4 8 5 9 5 3 9 9 10 10 5 7 1 1 10 3 7 7 8 1 10 6 3 7 8 4 10 10 1 6 5 5 4 7 9 10 10 7 4 9 3 8 1 8 1 5 9 1 10 6 5 7 6 1 1 7 3 10 4 8 9 8 6 7 1 2 3 8 9 10 5 1 10 10 6 6 1 3 6 8 8 3 6 7 3 6 1 2 ...

output:

520943

result:

ok 1 number(s): "520943"

Test #84:

score: 0
Accepted
time: 339ms
memory: 73824kb

input:

1000000
999990 5 6 4 5 6 9 5 4 5 9 8 4 1 5 10 7 3 2 4 9 9 8 1 7 8 10 10 3 4 7 8 5 4 6 10 1 4 4 1 3 2 1 6 10 7 8 7 2 10 8 10 4 2 3 10 7 5 2 1 1 10 4 10 6 5 9 2 3 4 9 10 8 5 4 1 5 3 6 3 6 6 10 6 3 1 1 8 6 8 10 8 6 2 10 8 3 6 9 4 10 6 4 10 8 7 1 3 7 2 5 2 5 10 6 7 10 6 5 10 5 10 3 9 3 2 6 7 5 2 4 10 4 ...

output:

490880

result:

ok 1 number(s): "490880"

Test #85:

score: 0
Accepted
time: 359ms
memory: 73804kb

input:

1000000
999992 3 1 6 5 7 4 1 8 3 6 9 8 10 6 1 1 10 10 5 9 2 9 7 10 7 5 3 2 4 10 2 10 1 7 6 5 4 10 8 6 1 10 2 3 10 7 3 6 4 2 8 5 1 3 2 6 4 9 7 6 3 5 9 3 10 8 3 4 8 6 3 5 3 9 1 3 6 1 5 1 5 3 2 10 3 9 2 6 9 2 7 9 7 3 6 5 5 1 8 6 1 3 9 3 5 10 8 1 5 1 3 1 1 8 4 10 9 10 1 1 5 6 10 3 10 6 9 3 10 10 9 1 9 4...

output:

476291

result:

ok 1 number(s): "476291"

Test #86:

score: 0
Accepted
time: 649ms
memory: 73772kb

input:

1000000
999999 999998 999996 999991 999991 999987 999985 999985 999981 999979 999978 999976 999974 999974 999969 999968 999964 999963 999962 999961 999959 999956 999954 999946 999945 999944 999943 999940 999940 999939 999938 999936 999929 999917 999915 999914 999914 999911 999910 999910 999905 99989...

output:

619296

result:

ok 1 number(s): "619296"

Test #87:

score: 0
Accepted
time: 628ms
memory: 73676kb

input:

1000000
999999 999997 999997 999993 999992 999991 999990 999989 999987 999987 999983 999982 999968 999966 999966 999966 999963 999962 999958 999956 999951 999950 999947 999945 999941 999941 999939 999938 999936 999933 999932 999926 999924 999914 999914 999912 999911 999908 999907 999907 999906 99990...

output:

78905

result:

ok 1 number(s): "78905"

Test #88:

score: 0
Accepted
time: 619ms
memory: 73840kb

input:

1000000
1000000 999990 999988 999988 999988 999988 999982 999982 999980 999972 999971 999970 999965 999964 999962 999961 999961 999961 999960 999959 999958 999954 999953 999948 999947 999946 999944 999943 999941 999939 999939 999938 999934 999933 999929 999929 999926 999925 999917 999914 999914 9999...

output:

236481

result:

ok 1 number(s): "236481"

Test #89:

score: 0
Accepted
time: 601ms
memory: 73988kb

input:

1000000
2 2 220083 13 14 23 23 24 31 32 33 35 36 36 36 37 44 49 50 50 52 54 58 944417 69 732805 77 78 79 64056 80 980556 97 104 105 106 107 981996 109 113 118 914633 923360 134 145 80088 146 152 153 153 7110 830323 982629 160 160 166 167 890688 169 170 354803 174 176 180 182 183 191 131808 273580 19...

output:

557396

result:

ok 1 number(s): "557396"

Test #90:

score: 0
Accepted
time: 608ms
memory: 73780kb

input:

1000000
1 3 3 5 6 10 11 427715 15 568235 340254 20 25 609015 26 32 34 38 510361 41 42 43 43 43 46 47 49 51 54 55 58 62 62 67 70 72 73 76 48169 76 77 79 81 82 166672 85 87 88 91 91 95 95 97 26227 99 100 100 101 102 104 772543 112 112 115 874154 111683 121 407458 123 586905 132 137 139 141 433244 145 ...

output:

308000

result:

ok 1 number(s): "308000"

Test #91:

score: 0
Accepted
time: 612ms
memory: 73916kb

input:

1000000
4 13 464623 14 15 17 446168 22 23 28 28 29 30 33 33 34 35 743285 40 44 50 52 781787 859463 56 58 60 61 62 64 65 761553 70 991292 72 333172 79 112128 624055 86 86 88 91 837782 95 924059 100 101 105 110 111 114 116 116 119 122 123 123 123 124 126 131 131 362630 134 137 139 144 145 145 942101 1...

output:

951926

result:

ok 1 number(s): "951926"

Subtask #7:

score: 4
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #92:

score: 4
Accepted
time: 330ms
memory: 73936kb

input:

1000000
999999997 10 7 5 10 3 6 9 5 1 10 7 8 2 2 9 6 1 3 1 2 6 1 5 9 3 2 4 3 8 7 6 8 1 2 3 8 4 9 8 5 3 6 7 10 2 7 3 2 8 3 8 4 9 1 10 10 5 6 1 9 4 4 9 7 2 6 8 7 9 6 9 4 9 4 3 1 7 1 4 2 7 2 3 8 9 2 9 8 4 4 4 7 9 3 6 6 2 6 10 7 7 2 4 3 6 3 4 8 8 6 7 3 10 10 9 1 1 3 2 5 8 2 9 4 8 9 4 10 3 1 8 9 8 1 4 1 ...

output:

492833

result:

ok 1 number(s): "492833"

Test #93:

score: 0
Accepted
time: 776ms
memory: 73824kb

input:

1000000
999999665 999999594 999999211 999999139 999996077 999995302 999994629 999990757 999989701 999984488 999979447 999978575 999975078 999967310 999964202 999963570 999957476 999956866 999950703 999949934 999949346 999946790 999946493 999943373 999941400 999935118 999935027 999933207 999932256 99...

output:

307470

result:

ok 1 number(s): "307470"

Test #94:

score: 0
Accepted
time: 756ms
memory: 73728kb

input:

1000000
999999294 999994470 999993081 999990419 999987398 999986030 999985165 999985152 999978647 999975608 999973460 999970171 999968874 999968812 999961180 999959074 999954631 999951767 999950962 999950861 999948310 999948245 999946341 999943164 999942661 999941530 999938184 999937984 999937054 99...

output:

207900

result:

ok 1 number(s): "207900"

Test #95:

score: 0
Accepted
time: 765ms
memory: 73688kb

input:

1000000
999998202 999996804 999987481 999987434 999978003 999975388 999974399 999963911 999962880 999962072 999958992 999956222 999945361 999942458 999941627 999934236 999933282 999933180 999931305 999930082 999927189 999926891 999926281 999916560 999916489 999913765 999913735 999913469 999909441 99...

output:

682433

result:

ok 1 number(s): "682433"

Test #96:

score: 0
Accepted
time: 633ms
memory: 73860kb

input:

1000000
6 268 1843 2094 5534 7863 8375 14578 15755 20187 22918 507796015 26472 28476 29184 32234 33047 33098 894589580 46995 89396852 53599 53809 57866 60910 64676 66920 67338 67659 68708 69926 70218 71443 131829821 74019 76779 535620725 733594507 78662 79525 80340 82436 84544 190212411 85032 85648 ...

output:

327729

result:

ok 1 number(s): "327729"

Test #97:

score: 0
Accepted
time: 665ms
memory: 74116kb

input:

1000000
562 1961 2796 875431737 5316 5826 554160291 7133 13079 13156 14693 17680 612900809 20071 91972165 28801 331773198 34274 35186 35379 36126 36139 39402 879828626 44748 48342 50417 53245 56972 59601 85320778 548203713 67663 67797 70300 70525 71341 72847 75093 76123 73028182 81576 86088 87486 87...

output:

852078

result:

ok 1 number(s): "852078"

Test #98:

score: 0
Accepted
time: 646ms
memory: 73848kb

input:

1000000
2823 2921 7540 147019629 15984 18875 20977 25051 337125642 27976 82093793 30567 36514 37938 40072 45254 46173 48597 54804 55174 55719 55952 56560 62745 63917 66043 177350677 68510 75066 76487 77231 78058 79303 79493 80505 81844 81910 81952 84476 86268 658997572 98143 99118 190699125 74191316...

output:

449514

result:

ok 1 number(s): "449514"

Test #99:

score: 0
Accepted
time: 1128ms
memory: 73632kb

input:

1000000
550539514 7467131 932880667 394274428 584242598 202485380 117533543 821743585 772740987 514806801 160682717 610117748 545934144 48806210 28300574 792270270 717451536 61327275 394855008 961974271 423717084 629275350 681447404 445824681 147939559 893444799 769539233 618456290 37040200 92059503...

output:

470311

result:

ok 1 number(s): "470311"

Test #100:

score: 0
Accepted
time: 1137ms
memory: 73672kb

input:

1000000
667423386 138950990 634067410 368644950 455150240 658006603 682728856 478559597 551806831 232502619 781389573 698814900 903101349 23979776 806330251 714822353 729171110 761855525 521424286 522710030 571620631 304094868 166339895 223950298 715560294 168358782 351412308 38031430 158550079 2829...

output:

587004

result:

ok 1 number(s): "587004"

Test #101:

score: 0
Accepted
time: 1050ms
memory: 73904kb

input:

1000000
71973561 121463665 669683554 685207962 553885061 350197039 743420556 57606953 332037942 115949003 705054671 741273078 359325090 745585594 406030252 477325872 172227217 290103942 269368787 206771802 986044993 493804364 736026541 674386894 898958305 551966525 196006610 140426037 35459606 41705...

output:

242839

result:

ok 1 number(s): "242839"

Test #102:

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

input:

1000000
893890137 547914820 930678808 659578485 869503103 510750966 163391676 419455669 111103787 538677525 30794232 979713334 716492296 720759161 743868441 399877954 478914087 430823680 395938065 62474858 693757052 873656586 220919031 157545214 171611744 976623613 482912389 119809688 11745293 52475...

output:

760603

result:

ok 1 number(s): "760603"

Test #103:

score: 0
Accepted
time: 1089ms
memory: 73820kb

input:

1000000
133173113 563528649 2468853 441499622 662326672 584378785 202964522 449007633 478938957 385590072 758608255 414135669 529892567 944981565 995195090 482478602 883946854 448855954 311197527 645108796 985205194 293908431 61208855 413102956 943586019 997619646 917162348 151532655 937664038 49661...

output:

872666

result:

ok 1 number(s): "872666"

Test #104:

score: 0
Accepted
time: 334ms
memory: 73620kb

input:

1000000
999999993 1 3 10 1 7 9 3 6 7 7 10 7 1 4 1 5 9 2 5 3 2 2 2 5 6 4 10 10 10 3 7 4 3 10 4 9 6 10 2 7 4 2 10 4 1 4 5 2 3 9 3 2 10 9 2 2 9 3 1 5 8 2 2 1 1 5 10 7 5 2 10 2 1 7 3 7 3 9 10 7 4 1 1 4 3 2 6 6 6 6 3 7 3 4 2 1 3 10 4 7 2 6 6 2 10 8 4 6 5 7 1 9 7 4 9 10 2 7 2 6 7 2 6 6 4 8 7 5 9 9 8 10 7 ...

output:

333054

result:

ok 1 number(s): "333054"

Test #105:

score: 0
Accepted
time: 341ms
memory: 73808kb

input:

1000000
999999991 7 10 6 10 10 4 5 10 4 7 6 3 2 5 1 10 8 10 3 5 5 3 7 8 6 3 9 8 9 10 7 1 6 4 10 9 1 7 6 7 6 7 5 6 5 2 9 8 6 1 1 9 10 7 3 1 8 8 7 7 3 7 4 8 4 6 7 8 1 5 10 7 8 2 9 7 4 6 2 5 8 5 6 7 5 5 10 7 8 8 6 5 4 7 4 3 8 4 9 4 8 5 1 8 4 9 9 10 10 7 6 1 6 10 8 4 5 9 5 1 6 4 2 6 2 10 10 7 4 5 2 2 4 ...

output:

224938

result:

ok 1 number(s): "224938"

Extra Test:

score: 0
Extra Test Passed