QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#883259#10052. Just Long Neckties 2ProjectCF72 1052ms31360kbC++142.0kb2025-02-05 15:32:572025-02-05 15:32:58

Judging History

This is the latest submission verdict.

  • [2025-02-05 15:32:58]
  • Judged
  • Verdict: 72
  • Time: 1052ms
  • Memory: 31360kb
  • [2025-02-05 15:32:57]
  • Submitted

answer

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <time.h>
#include <map>
#include <complex>
#include <math.h>
#include <stack>
#include <unordered_map>
#include <set>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <random>
using namespace std;
//#define int long long
#define P make_pair
#define A first
#define B second
typedef pair<int, int> pii;
int dp[1 << 21], a[5000010];
signed main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i < (1 << 21); i++)dp[i] = -1;
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < (1 << 21); i++) {
        if (dp[i] == -1)continue;
        while (dp[i] < n) {
            if (i & (1 << (a[dp[i] + 1] - 1)))dp[i]++;
            else if (dp[i] < n - 1 && i & (1 << (a[dp[i] + 2] - 1)))dp[i] += 2;
            else break;
        }
        if (dp[i] < n) {
            int h1 = a[dp[i] + 1] - 1;
            int ok = 0;
            for (int t = h1; t >= 0; t--)if (i & (1 << t)) {
                dp[i - (1 << t) + (1 << h1)] = max(dp[i - (1 << t) + (1 << h1)], dp[i] + 1);
                ok = 1;
                break;
            }
            if (!ok)dp[i + (1 << h1)] = max(dp[i + (1 << h1)], dp[i] + 1);
        }
        if (dp[i] < n - 1) {
            int h1 = a[dp[i] + 2] - 1;
            int ok = 0;
            for (int t = h1; t >= 0; t--)if (i & (1 << t)) {
                dp[i - (1 << t) + (1 << h1)] = max(dp[i - (1 << t) + (1 << h1)], dp[i] + 2);
                ok = 1;
                break;
            }
            if (!ok)dp[i + (1 << h1)] = max(dp[i + (1 << h1)], dp[i] + 2);
        }
        if (dp[i] >= n - 1) {
            int t = 0;
            for (int h = 0; h <= 20; h++)if (i & (1 << h))t++;
            ans = min(ans, t);
        }
    }
    cout << ans << endl;
    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 2ms
memory: 13152kb

input:

15
2 19 3 6 1 18 20 9 17 19 18 4 15 7 16

output:

3

result:

ok single line: '3'

Test #2:

score: 10
Accepted
time: 1ms
memory: 12768kb

input:

15
13 6 13 10 3 6 18 8 20 14 11 15 12 12 15

output:

2

result:

ok single line: '2'

Test #3:

score: 10
Accepted
time: 2ms
memory: 13620kb

input:

15
3 6 7 9 10 6 12 13 5 13 14 16 17 6 18

output:

1

result:

ok single line: '1'

Test #4:

score: 10
Accepted
time: 2ms
memory: 13788kb

input:

13
14 2 12 4 16 5 7 7 19 8 5 8 20

output:

1

result:

ok single line: '1'

Test #5:

score: 10
Accepted
time: 2ms
memory: 13792kb

input:

15
6 14 13 5 17 16 15 6 20 17 9 21 10 4 20

output:

2

result:

ok single line: '2'

Test #6:

score: 10
Accepted
time: 3ms
memory: 12256kb

input:

15
21 21 21 14 13 16 15 14 7 6 5 3 7 5 1

output:

4

result:

ok single line: '4'

Test #7:

score: 10
Accepted
time: 1ms
memory: 12900kb

input:

15
5 15 16 17 21 21 21 21 21 13 21 21 21 1 21

output:

1

result:

ok single line: '1'

Test #8:

score: 10
Accepted
time: 2ms
memory: 13008kb

input:

15
8 8 8 8 8 8 8 8 8 8 8 8 8 8 14

output:

1

result:

ok single line: '1'

Test #9:

score: 10
Accepted
time: 2ms
memory: 13008kb

input:

15
17 17 17 6 6 17 17 17 6 17 6 17 6 6 17

output:

2

result:

ok single line: '2'

Test #10:

score: 10
Accepted
time: 2ms
memory: 12132kb

input:

15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

output:

1

result:

ok single line: '1'

Test #11:

score: 10
Accepted
time: 2ms
memory: 12384kb

input:

15
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7

output:

7

result:

ok single line: '7'

Test #12:

score: 10
Accepted
time: 2ms
memory: 13664kb

input:

15
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8

output:

1

result:

ok single line: '1'

Test #13:

score: 10
Accepted
time: 2ms
memory: 12768kb

input:

15
21 21 20 20 19 19 18 18 17 17 16 16 15 15 14

output:

7

result:

ok single line: '7'

Test #14:

score: 10
Accepted
time: 2ms
memory: 11820kb

input:

2
21 21

output:

1

result:

ok single line: '1'

Test #15:

score: 10
Accepted
time: 1ms
memory: 13540kb

input:

15
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21

output:

1

result:

ok single line: '1'

Test #16:

score: 10
Accepted
time: 2ms
memory: 13020kb

input:

15
21 9 10 16 4 4 10 20 5 2 4 1 11 16 9

output:

3

result:

ok single line: '3'

Test #17:

score: 10
Accepted
time: 0ms
memory: 12896kb

input:

15
14 9 8 19 5 19 8 9 3 2 20 16 10 16 15

output:

3

result:

ok single line: '3'

Test #18:

score: 10
Accepted
time: 2ms
memory: 12896kb

input:

2
1 1

output:

1

result:

ok single line: '1'

Subtask #2:

score: 6
Accepted

Test #19:

score: 6
Accepted
time: 2ms
memory: 12388kb

input:

500
1 1 2 2 2 2 2 1 2 2 1 1 1 1 2 1 1 2 1 2 1 2 1 1 2 2 2 2 1 1 1 2 2 1 1 1 2 1 1 1 1 1 2 1 2 2 1 2 1 2 2 1 2 1 1 2 2 1 2 1 2 1 1 1 1 2 2 1 2 1 1 2 1 2 2 1 1 1 2 1 2 1 1 2 2 2 1 2 2 2 2 1 1 2 1 2 1 2 1 2 1 2 1 2 2 2 1 2 2 2 2 2 2 1 1 1 2 1 1 2 1 2 2 2 1 1 1 1 2 2 2 2 1 1 2 2 1 2 2 1 2 2 2 1 2 2 1 1 ...

output:

2

result:

ok single line: '2'

Test #20:

score: 6
Accepted
time: 2ms
memory: 12512kb

input:

500
1 2 1 1 2 2 1 2 1 1 2 1 2 1 1 1 1 2 2 1 1 2 2 2 1 1 1 1 2 2 1 2 1 2 2 2 1 1 2 2 2 1 1 1 1 2 1 1 2 1 1 2 2 1 2 2 1 1 1 1 2 2 2 2 1 1 2 1 2 2 2 2 2 1 2 2 1 1 2 1 2 2 1 1 1 2 1 2 1 2 1 2 1 1 1 2 2 1 1 1 1 2 2 2 2 1 1 1 1 1 2 1 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 1 1 2 2 1 2 2 2 1 1 1 2 2 1 1 2 2 2 2 1 1 ...

output:

2

result:

ok single line: '2'

Test #21:

score: 6
Accepted
time: 2ms
memory: 11876kb

input:

500
2 1 2 2 2 2 2 2 2 1 2 2 1 2 1 2 1 2 1 2 2 1 2 1 2 2 2 1 2 2 1 2 2 2 2 1 2 2 1 2 1 2 2 2 2 2 1 2 1 2 1 2 1 2 2 2 1 2 1 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 1 2 1 2 1 2 1 2 2 1 2 1 2 2 2 1 2 1 2 2 1 2 2 1 2 2 2 2 2 1 2 1 2 2 1 2 2 2 1 2 2 1 2 1 2 1 2 1 2 2 1 2 2 1 2 1 2 1 2 1 2 1 2 2 2 1 2 1 2 2 2 2 1 2 ...

output:

1

result:

ok single line: '1'

Test #22:

score: 6
Accepted
time: 1ms
memory: 11868kb

input:

500
2 1 2 1 2 1 1 2 1 2 1 1 2 1 1 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 2 1 1 2 1 1 1 2 1 1 2 1 1 2 1 2 1 1 2 1 2 1 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 2 1 1 1 2 1 1 2 1 2 1 2 1 1 1 2 1 1 2 1 2 1 2 1 1 2 1 2 1 2 1 1 2 1 1 1 1 1 2 1 2 1 2 1 2 1 1 2 1 1 1 1 2 1 1 1 1 2 ...

output:

1

result:

ok single line: '1'

Test #23:

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

input:

500
2 1 1 2 1 1 2 1 2 1 1 1 2 1 2 1 2 1 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 2 1 1 1 2 1 2 1 2 1 2 1 1 1 2 1 2 1 2 1 2 1 1 2 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 1 1 1 1 1 1 2 1 1 1 1 2 1 2 1 2 1 2 1 2 1 1 1 2 1 1 1 2 1 1 2 1 1 2 1 1 2 1 2 1 1 2 1 1 1 2 1 2 1 2 1 1 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 2 ...

output:

1

result:

ok single line: '1'

Test #24:

score: 6
Accepted
time: 2ms
memory: 13024kb

input:

500
2 1 2 1 2 1 2 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 2 1 2 1 2 1 1 2 1 1 1 1 1 1 2 1 2 1 1 2 1 1 2 1 1 2 1 2 1 2 1 2 1 1 1 1 2 1 2 1 1 1 2 1 2 1 2 1 2 1 2 1 1 1 2 1 1 2 1 1 1 1 2 1 1 2 1 1 1 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 1 2 1 2 1 2 1 2 1 1 2 1 1 1 1 2 1 1 1 ...

output:

1

result:

ok single line: '1'

Test #25:

score: 6
Accepted
time: 1ms
memory: 12128kb

input:

500
1 2 1 1 2 1 1 2 1 1 2 1 2 1 2 1 1 2 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1 2 1 2 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 1 2 1 1 2 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 1 1 1 1 2 1 2 1 1 2 1 1 1 2 1 1 2 1 2 1 1 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 2 1 2 ...

output:

1

result:

ok single line: '1'

Test #26:

score: 6
Accepted
time: 1ms
memory: 12640kb

input:

2
1 2

output:

1

result:

ok single line: '1'

Test #27:

score: 6
Accepted
time: 2ms
memory: 13408kb

input:

2
2 1

output:

1

result:

ok single line: '1'

Test #28:

score: 6
Accepted
time: 2ms
memory: 12636kb

input:

4
1 1 2 2

output:

1

result:

ok single line: '1'

Test #29:

score: 6
Accepted
time: 2ms
memory: 12000kb

input:

4
2 2 1 1

output:

2

result:

ok single line: '2'

Test #30:

score: 6
Accepted
time: 2ms
memory: 13024kb

input:

500
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

1

result:

ok single line: '1'

Test #31:

score: 6
Accepted
time: 2ms
memory: 13796kb

input:

500
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:

2

result:

ok single line: '2'

Test #32:

score: 6
Accepted
time: 2ms
memory: 11876kb

input:

2
2 2

output:

1

result:

ok single line: '1'

Test #33:

score: 6
Accepted
time: 2ms
memory: 11704kb

input:

500
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:

1

result:

ok single line: '1'

Subtask #3:

score: 12
Accepted

Test #34:

score: 12
Accepted
time: 2ms
memory: 12644kb

input:

500
2 5 4 4 4 1 1 4 5 1 1 2 2 1 4 3 3 1 4 5 4 3 1 1 3 4 4 2 2 3 1 1 1 1 3 3 5 2 1 2 1 1 4 1 4 4 1 2 2 5 3 4 2 3 2 3 5 3 3 1 5 3 4 5 1 2 5 5 2 1 5 1 4 2 2 2 1 2 1 2 2 1 4 2 3 5 1 2 5 2 1 2 5 3 3 5 3 1 3 4 3 3 1 3 4 4 5 1 2 2 2 3 2 5 3 5 3 1 4 5 1 1 5 3 3 5 4 3 1 5 1 5 5 1 5 5 2 4 3 2 5 3 3 2 4 3 1 3 ...

output:

5

result:

ok single line: '5'

Test #35:

score: 12
Accepted
time: 2ms
memory: 12512kb

input:

500
4 5 3 3 2 5 3 2 4 3 5 4 1 5 2 2 2 4 2 1 5 5 5 1 1 2 3 1 4 4 2 3 3 3 1 4 4 1 2 1 1 1 4 2 3 1 4 1 3 3 5 4 5 2 3 5 1 5 1 2 2 5 2 2 5 1 4 2 4 2 2 1 4 5 3 2 2 2 2 2 3 1 1 5 2 4 2 4 2 2 3 2 5 3 2 1 2 5 5 2 3 1 4 5 1 4 4 4 1 3 4 1 1 3 2 5 1 4 4 2 3 1 5 5 4 2 4 1 4 3 2 1 3 4 4 3 1 3 2 5 3 3 5 5 4 4 4 5 ...

output:

5

result:

ok single line: '5'

Test #36:

score: 12
Accepted
time: 1ms
memory: 13788kb

input:

500
1 1 4 1 1 3 1 1 3 1 5 1 1 1 5 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 3 1 1 1 1 4 1 1 2 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 4 1 3 1 1 1 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 2 2 1 2 2 2 2 2 2 5 2 2 1 2 3 2 2 1 2 2 2 2 2 5 2 2 1 ...

output:

1

result:

ok single line: '1'

Test #37:

score: 12
Accepted
time: 2ms
memory: 13028kb

input:

499
4 1 1 1 2 1 3 1 2 1 2 1 1 1 4 1 2 1 5 1 3 1 1 1 4 1 5 1 5 1 5 1 1 1 3 1 4 1 5 1 2 1 3 1 1 1 1 1 2 1 3 1 3 1 1 1 2 1 2 1 5 1 3 1 4 1 1 1 3 1 2 1 4 1 1 1 3 1 5 1 1 1 5 1 4 1 2 1 5 1 4 1 4 1 3 1 4 1 3 1 5 1 2 1 1 2 5 2 4 2 4 2 1 2 1 2 3 2 1 2 4 2 2 2 4 2 3 2 5 2 3 2 5 2 1 2 5 2 4 2 2 2 5 2 5 2 2 2 ...

output:

1

result:

ok single line: '1'

Test #38:

score: 12
Accepted
time: 2ms
memory: 12000kb

input:

500
1 1 2 1 1 1 3 1 1 1 4 1 3 1 1 1 1 1 1 3 1 2 1 1 4 1 1 5 1 1 1 2 1 1 1 5 1 4 1 5 1 1 1 1 1 1 1 1 2 1 4 1 1 1 1 1 1 4 1 5 1 3 1 4 1 1 1 1 1 1 1 5 1 1 5 2 3 1 4 1 1 1 1 1 1 2 1 2 2 1 2 3 2 4 2 2 2 4 2 2 2 1 3 2 2 1 5 1 5 2 2 2 2 5 2 4 2 4 1 5 1 1 1 2 4 2 4 2 5 1 1 2 2 1 2 5 2 3 2 4 2 2 5 2 2 2 3 2 ...

output:

3

result:

ok single line: '3'

Test #39:

score: 12
Accepted
time: 2ms
memory: 12116kb

input:

500
5 4 5 5 5 5 5 5 4 4 5 5 4 5 4 4 5 5 5 5 5 5 5 5 5 4 5 5 5 4 5 5 4 5 4 5 4 4 5 5 5 4 5 4 5 5 5 4 5 5 5 4 5 5 5 5 4 5 4 4 4 5 4 5 5 5 5 5 4 5 5 5 5 5 5 5 4 5 4 4 4 4 5 5 5 5 5 4 5 4 5 5 4 5 5 5 5 5 4 5 5 5 3 3 3 3 5 5 3 5 3 4 3 4 4 3 4 3 5 5 5 4 3 4 4 4 5 3 3 4 4 5 3 5 3 5 3 4 4 5 5 3 5 4 3 3 5 4 ...

output:

5

result:

ok single line: '5'

Test #40:

score: 12
Accepted
time: 0ms
memory: 12892kb

input:

500
4 4 1 4 5 4 4 4 2 4 4 4 3 5 5 5 5 4 4 1 1 1 5 3 5 4 4 5 4 4 5 2 4 2 1 1 4 2 5 2 4 4 5 4 1 4 5 4 4 4 4 4 4 4 2 4 5 1 2 5 1 2 4 5 3 3 1 3 4 3 4 1 3 2 2 4 4 3 4 2 1 5 2 3 4 4 4 4 5 3 4 5 5 1 4 1 4 1 4 4 4 2 4 3 2 3 5 1 4 3 1 4 1 3 4 5 2 4 2 1 3 4 1 4 4 4 1 4 2 4 4 5 2 4 5 4 5 4 4 4 4 4 2 4 5 4 4 2 ...

output:

5

result:

ok single line: '5'

Test #41:

score: 12
Accepted
time: 1ms
memory: 12896kb

input:

500
1 4 1 1 1 1 1 1 1 1 1 3 1 1 1 3 1 1 1 1 1 1 3 1 1 4 1 1 1 2 4 1 3 1 5 1 1 1 1 1 2 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 3 2 1 5 5 1 2 1 1 1 4 1 1 1 1 1 1 5 5 1 1 1 1 5 2 1 1 2 5 3 1 1 1 1 3 1 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 2 1 3 1 2 1 1 1 1 1 1 1 3 4 3 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 1 1 1 ...

output:

4

result:

ok single line: '4'

Test #42:

score: 12
Accepted
time: 2ms
memory: 12508kb

input:

500
5 5 5 1 1 2 5 5 1 5 5 1 1 5 1 5 5 1 5 1 5 1 1 1 3 5 1 1 1 5 5 1 5 5 4 5 3 1 1 1 5 1 5 5 3 1 1 1 5 1 5 1 2 5 5 5 3 5 1 1 1 5 1 1 1 5 1 5 1 3 4 5 5 1 5 1 1 5 2 1 5 1 1 3 5 5 5 1 5 1 5 1 1 1 4 1 1 5 1 1 1 1 1 5 1 5 5 5 5 1 1 5 1 5 1 5 1 5 1 1 5 5 1 1 1 5 3 5 1 1 5 1 1 5 1 5 1 1 5 5 5 1 1 1 5 5 1 1 ...

output:

4

result:

ok single line: '4'

Test #43:

score: 12
Accepted
time: 2ms
memory: 12928kb

input:

5
1 2 3 4 5

output:

1

result:

ok single line: '1'

Test #44:

score: 12
Accepted
time: 2ms
memory: 13668kb

input:

5
5 4 3 2 1

output:

2

result:

ok single line: '2'

Test #45:

score: 12
Accepted
time: 1ms
memory: 13104kb

input:

10
1 1 2 2 3 3 4 4 5 5

output:

1

result:

ok single line: '1'

Test #46:

score: 12
Accepted
time: 2ms
memory: 13020kb

input:

10
5 5 4 4 3 3 2 2 1 1

output:

5

result:

ok single line: '5'

Test #47:

score: 12
Accepted
time: 3ms
memory: 12000kb

input:

500
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 2 ...

output:

1

result:

ok single line: '1'

Test #48:

score: 12
Accepted
time: 3ms
memory: 12256kb

input:

500
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

output:

5

result:

ok single line: '5'

Test #49:

score: 12
Accepted
time: 2ms
memory: 12256kb

input:

2
5 5

output:

1

result:

ok single line: '1'

Test #50:

score: 12
Accepted
time: 2ms
memory: 12212kb

input:

500
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...

output:

1

result:

ok single line: '1'

Test #51:

score: 12
Accepted
time: 1ms
memory: 13536kb

input:

500
1 1 3 1 3 1 3 1 3 1 2 1 2 1 5 1 3 1 4 1 2 1 3 2 5 1 2 2 4 2 3 1 2 1 1 1 3 1 5 1 1 1 4 1 5 1 4 1 5 2 3 1 3 1 1 1 3 2 5 2 5 1 1 1 1 1 2 4 2 4 3 5 1 3 2 4 2 3 2 3 2 3 1 3 1 2 2 2 1 2 3 1 2 5 1 2 2 1 2 3 2 3 1 3 2 2 3 1 2 5 2 4 1 2 2 4 2 3 1 3 3 1 2 3 1 2 2 4 2 1 2 3 2 5 3 1 3 4 4 2 3 3 3 5 2 5 3 4 ...

output:

4

result:

ok single line: '4'

Test #52:

score: 12
Accepted
time: 4ms
memory: 13340kb

input:

500
1 1 1 1 2 1 5 1 4 1 1 1 1 1 4 1 2 1 5 1 5 1 2 1 1 1 2 1 4 2 1 1 4 1 2 1 3 1 2 1 2 1 1 2 5 1 5 2 2 1 3 1 3 1 3 1 1 1 1 1 4 1 1 1 4 1 2 1 3 1 1 1 1 1 1 2 4 2 1 2 4 2 5 1 5 1 5 1 2 1 5 1 5 1 1 1 2 1 4 1 5 2 4 1 1 1 3 2 4 1 3 1 4 1 2 2 2 2 2 1 4 2 1 2 1 2 2 3 1 4 4 2 3 3 4 2 2 3 5 2 5 2 1 2 1 2 4 1 ...

output:

4

result:

ok single line: '4'

Subtask #4:

score: 18
Accepted

Test #53:

score: 18
Accepted
time: 2ms
memory: 12892kb

input:

500
2 1 12 3 13 13 7 9 7 3 14 10 9 13 6 3 9 1 10 10 7 13 6 9 10 13 3 7 15 12 14 4 1 5 4 3 8 7 3 14 5 1 6 13 1 3 4 10 5 8 3 6 2 4 10 1 13 5 6 13 12 10 14 15 8 9 13 10 9 14 4 9 13 12 4 7 12 4 2 14 6 12 5 4 6 12 13 6 2 12 10 5 6 5 1 1 5 1 5 12 11 3 6 13 11 10 1 8 14 9 5 5 15 1 15 3 15 10 4 6 9 14 1 5 1...

output:

10

result:

ok single line: '10'

Test #54:

score: 18
Accepted
time: 2ms
memory: 12892kb

input:

500
13 14 8 6 9 11 5 12 9 13 10 11 2 3 7 15 12 1 11 3 1 10 15 6 4 9 2 10 3 5 3 14 4 12 11 11 4 7 8 4 13 10 6 2 11 15 2 10 12 4 13 5 2 5 2 15 3 14 9 7 1 6 12 15 10 5 6 5 4 7 13 1 12 15 2 15 11 10 15 8 5 12 2 14 11 4 1 12 5 10 13 14 10 10 7 12 10 8 11 13 12 2 11 10 1 14 1 10 6 13 13 7 5 14 3 8 4 10 6 ...

output:

11

result:

ok single line: '11'

Test #55:

score: 18
Accepted
time: 3ms
memory: 12252kb

input:

500
1 7 1 1 1 9 1 8 1 13 1 1 8 1 1 6 1 1 10 1 7 1 1 1 1 15 1 2 1 8 1 2 1 2 2 2 8 2 4 2 2 2 2 6 2 2 2 2 2 2 2 2 2 10 2 2 2 2 2 14 2 2 2 2 9 2 2 6 2 3 3 11 3 3 10 3 3 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 9 3 12 3 1 4 7 4 4 4 4 4 6 4 4 4 12 4 4 5 4 4 4 4 4 4 4 4 4 4 13 4 5 4 5 ...

output:

1

result:

ok single line: '1'

Test #56:

score: 18
Accepted
time: 2ms
memory: 13792kb

input:

499
9 1 6 1 14 1 8 1 4 1 15 1 11 1 7 1 12 1 2 1 4 1 6 1 2 1 15 1 1 1 5 1 13 1 5 1 2 1 15 1 5 2 5 2 9 2 15 2 2 2 3 2 5 2 13 2 9 2 7 2 13 2 11 2 11 3 13 3 15 3 1 3 8 3 1 3 12 3 3 3 12 3 14 3 6 3 9 3 1 3 14 3 8 4 11 4 3 4 5 4 15 4 9 4 9 4 13 4 4 4 8 4 4 4 1 4 6 4 3 4 13 4 14 4 1 4 15 5 7 5 2 5 12 5 15 ...

output:

1

result:

ok single line: '1'

Test #57:

score: 18
Accepted
time: 2ms
memory: 11868kb

input:

500
6 1 7 1 1 2 2 10 2 1 1 1 14 2 9 1 1 12 2 8 2 1 1 14 3 5 1 2 2 12 3 8 1 1 3 3 2 13 4 2 1 11 1 13 2 1 4 3 2 2 12 1 2 12 3 12 2 4 10 1 10 2 9 2 11 2 2 2 9 2 1 2 4 3 15 2 3 14 3 2 2 7 4 3 11 2 9 3 9 3 4 13 3 7 3 11 3 3 4 6 5 3 5 15 3 3 4 3 2 4 4 4 3 4 14 4 6 3 4 5 5 4 4 4 3 5 6 4 6 5 4 6 5 15 5 11 4...

output:

4

result:

ok single line: '4'

Test #58:

score: 18
Accepted
time: 1ms
memory: 12380kb

input:

500
4 10 1 3 2 3 12 1 6 4 5 2 1 3 2 11 7 11 1 2 2 13 2 2 4 3 5 4 5 1 6 4 6 1 10 4 2 4 1 15 6 5 5 8 7 1 1 1 7 6 9 4 9 7 8 11 2 15 13 1 1 1 5 9 4 7 3 7 6 6 6 4 11 1 3 7 5 6 9 15 3 6 1 8 15 4 9 7 7 1 2 3 2 4 4 3 9 1 4 8 10 9 4 7 11 2 1 1 9 1 2 1 10 3 6 7 14 2 1 1 1 2 5 4 2 4 7 8 8 2 9 9 8 4 4 14 6 9 1 ...

output:

8

result:

ok single line: '8'

Test #59:

score: 18
Accepted
time: 3ms
memory: 13568kb

input:

500
12 14 3 10 7 6 9 5 3 5 4 3 11 4 5 2 4 11 11 2 10 1 2 5 4 9 12 9 10 8 2 6 3 2 5 6 8 8 5 6 8 4 15 5 2 13 2 6 7 4 6 6 8 3 7 5 12 4 9 2 14 8 11 4 11 2 9 2 2 6 1 2 8 5 3 4 1 9 12 6 1 9 10 4 10 14 6 3 2 11 9 3 4 10 12 12 11 14 15 1 1 10 4 4 3 12 1 12 9 3 4 13 7 5 11 5 9 2 13 14 8 2 4 6 9 7 11 9 2 12 1...

output:

9

result:

ok single line: '9'

Test #60:

score: 18
Accepted
time: 2ms
memory: 13536kb

input:

500
9 5 6 3 6 1 8 3 8 1 4 3 9 2 10 3 10 1 9 4 9 2 7 7 12 6 1 2 2 3 14 5 1 1 8 3 11 9 6 2 15 4 15 1 7 8 15 2 9 6 2 1 8 9 7 3 10 7 2 10 12 8 8 8 11 2 11 4 3 4 6 1 4 3 9 14 2 2 13 6 5 2 14 7 5 1 3 7 12 1 1 5 13 4 14 10 15 13 6 12 1 2 2 7 2 9 12 3 3 4 8 10 1 6 1 7 2 10 3 6 4 4 11 10 13 7 7 11 2 15 8 3 1...

output:

8

result:

ok single line: '8'

Test #61:

score: 18
Accepted
time: 2ms
memory: 11868kb

input:

500
10 15 4 2 4 11 1 12 6 5 1 13 13 1 9 1 10 1 4 9 7 15 7 13 7 3 14 1 13 14 1 15 9 13 10 8 15 4 8 12 7 9 7 14 10 15 11 5 14 12 14 1 13 10 3 14 15 5 4 6 6 11 9 7 10 6 8 7 4 4 2 10 6 1 15 7 2 15 7 14 11 3 9 7 5 9 4 6 11 7 1 15 10 10 6 5 8 3 8 12 5 9 1 9 2 9 2 1 5 9 6 9 7 1 5 13 3 2 9 3 6 6 5 5 1 6 14 ...

output:

10

result:

ok single line: '10'

Test #62:

score: 18
Accepted
time: 4ms
memory: 13152kb

input:

500
15 15 14 15 15 15 14 13 15 15 13 13 13 15 15 15 15 15 15 14 15 15 15 15 15 14 15 15 15 15 15 13 15 13 15 14 15 15 13 13 12 13 15 12 15 14 13 13 15 15 14 12 15 13 12 15 14 15 12 14 14 15 12 15 13 12 13 12 12 12 13 12 14 15 15 14 13 13 13 12 11 13 13 12 15 15 11 14 12 13 11 15 13 12 13 13 11 11 15...

output:

14

result:

ok single line: '14'

Test #63:

score: 18
Accepted
time: 2ms
memory: 12128kb

input:

500
15 1 9 8 1 6 7 9 9 9 9 9 9 9 13 13 9 9 10 9 9 9 9 9 9 11 9 9 12 6 15 9 12 4 6 9 9 2 9 12 8 9 9 9 1 9 12 9 15 13 5 1 9 15 9 8 9 1 14 11 14 9 14 9 9 9 11 7 9 9 2 10 9 5 11 8 9 9 4 9 9 9 9 9 8 9 1 9 2 8 9 14 2 8 9 9 4 9 1 4 1 9 9 8 3 5 9 11 9 9 9 9 9 9 8 1 9 9 9 1 9 9 11 12 15 9 9 9 10 3 9 9 9 9 9 ...

output:

8

result:

ok single line: '8'

Test #64:

score: 18
Accepted
time: 3ms
memory: 12128kb

input:

500
8 3 15 8 8 15 8 8 8 8 8 3 3 8 8 8 4 8 8 8 4 8 8 8 15 8 8 8 8 8 8 8 8 8 8 1 8 8 8 8 8 8 8 8 8 8 8 6 8 8 8 8 8 8 8 8 8 8 8 8 8 15 8 3 8 8 8 8 8 8 8 10 8 14 8 8 8 6 2 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 10 11 8 8 8 4 8 2 8 8 8 8 8 8 8 8 8 8 8 14 8 8 8 8 3 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 8 15 8 ...

output:

4

result:

ok single line: '4'

Test #65:

score: 18
Accepted
time: 3ms
memory: 12516kb

input:

500
6 3 5 6 3 6 6 6 3 6 6 3 3 6 6 3 4 6 6 3 3 3 3 6 14 6 3 3 6 6 6 3 6 3 6 6 3 6 3 6 3 6 3 11 6 3 3 6 5 10 15 3 6 3 6 6 6 6 6 3 3 3 3 3 3 6 6 6 6 3 3 12 6 3 3 6 6 6 6 3 6 3 6 3 3 6 6 3 5 3 3 3 3 6 4 6 6 6 6 6 3 6 6 6 3 3 3 3 3 3 3 3 6 3 2 6 3 3 6 3 3 6 3 3 6 3 3 6 6 6 6 3 3 15 9 3 6 3 6 6 3 6 3 3 3 ...

output:

4

result:

ok single line: '4'

Test #66:

score: 18
Accepted
time: 2ms
memory: 13408kb

input:

15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

output:

7

result:

ok single line: '7'

Test #67:

score: 18
Accepted
time: 2ms
memory: 13412kb

input:

30
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

output:

1

result:

ok single line: '1'

Test #68:

score: 18
Accepted
time: 1ms
memory: 13284kb

input:

30
15 15 14 14 13 13 12 12 11 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1

output:

15

result:

ok single line: '15'

Test #69:

score: 18
Accepted
time: 2ms
memory: 12764kb

input:

495
1 1 1 1 1 1 1 1 1 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 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 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...

output:

1

result:

ok single line: '1'

Test #70:

score: 18
Accepted
time: 2ms
memory: 13752kb

input:

495
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13...

output:

15

result:

ok single line: '15'

Test #71:

score: 18
Accepted
time: 2ms
memory: 13152kb

input:

2
15 15

output:

1

result:

ok single line: '1'

Test #72:

score: 18
Accepted
time: 2ms
memory: 12124kb

input:

500
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15...

output:

1

result:

ok single line: '1'

Subtask #5:

score: 26
Accepted

Test #73:

score: 26
Accepted
time: 23ms
memory: 14916kb

input:

500000
13 6 2 6 3 6 13 5 9 8 4 12 10 7 1 7 10 14 15 15 1 9 4 4 1 14 3 8 13 2 8 11 14 14 4 13 8 9 13 14 9 7 3 15 7 7 1 11 11 11 2 13 11 15 3 4 8 12 9 4 10 4 10 13 4 9 14 11 7 13 10 4 9 14 12 14 11 5 7 6 14 1 6 14 10 9 2 14 8 8 8 9 7 1 15 3 11 3 3 5 13 1 15 7 4 7 15 3 15 14 14 2 4 12 5 13 12 11 3 1 12...

output:

15

result:

ok single line: '15'

Test #74:

score: 26
Accepted
time: 22ms
memory: 14888kb

input:

500000
8 7 9 12 2 7 1 11 10 12 14 3 1 4 10 12 8 12 7 14 2 3 4 8 3 8 14 13 4 10 6 10 6 10 6 12 7 2 3 4 9 13 13 2 2 8 9 6 2 1 9 3 9 6 3 8 12 3 4 7 2 6 12 12 4 9 3 15 1 7 2 1 9 14 2 8 12 6 14 6 6 10 2 15 2 14 11 1 1 2 13 9 1 14 2 5 2 13 1 9 15 7 3 12 10 10 5 13 8 9 6 6 8 9 4 8 1 2 10 13 4 7 15 9 4 14 7...

output:

15

result:

ok single line: '15'

Test #75:

score: 26
Accepted
time: 23ms
memory: 14960kb

input:

500000
1 6 1 1 1 1 1 1 1 4 1 9 1 1 1 1 1 1 1 1 1 1 10 1 1 11 1 1 1 10 1 13 1 1 1 1 6 1 1 1 1 9 1 1 1 1 14 1 1 1 4 1 1 11 1 1 7 1 12 1 1 1 8 1 1 1 3 1 1 1 1 15 1 1 1 1 11 1 8 1 1 1 1 1 8 1 1 1 1 8 1 1 1 1 1 1 1 1 1 7 1 1 1 1 1 11 1 13 1 1 1 13 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 5 1 1 10 1 1 1 1 1 ...

output:

1

result:

ok single line: '1'

Test #76:

score: 26
Accepted
time: 44ms
memory: 15012kb

input:

499999
3 1 10 1 14 1 13 1 11 1 11 1 2 1 2 1 5 1 4 1 10 1 5 1 3 1 1 1 5 1 5 1 9 1 11 1 9 1 10 1 9 1 2 1 5 1 2 1 14 1 4 1 4 1 4 1 10 1 1 1 3 1 15 1 2 1 4 1 1 1 2 1 4 1 14 1 6 1 5 1 8 1 7 1 13 1 9 1 1 1 13 1 15 1 5 1 5 1 4 1 12 1 2 1 4 1 5 1 8 1 12 1 9 1 10 1 9 1 12 1 12 1 2 1 10 1 3 1 2 1 7 1 2 1 14 1...

output:

1

result:

ok single line: '1'

Test #77:

score: 26
Accepted
time: 196ms
memory: 16780kb

input:

500000
1 1 1 9 1 1 3 1 1 2 1 1 1 1 1 1 1 13 1 12 1 4 1 3 1 12 1 8 1 1 12 1 1 1 6 1 6 1 15 1 11 1 1 1 13 1 1 8 1 1 1 1 5 1 6 1 1 14 1 13 1 5 1 6 1 1 1 1 1 8 1 12 1 8 1 13 1 8 1 1 1 7 1 12 1 1 1 5 1 12 1 3 1 2 1 5 1 8 1 1 1 12 1 13 1 13 1 1 12 1 8 1 9 1 1 14 1 10 1 12 1 14 1 1 1 8 1 3 1 1 1 1 1 10 1 1...

output:

2

result:

ok single line: '2'

Test #78:

score: 26
Accepted
time: 31ms
memory: 16880kb

input:

500000
1 1 1 1 1 1 9 1 1 6 1 1 1 1 1 1 1 1 1 1 1 13 1 1 1 1 1 1 1 1 1 1 1 1 15 1 1 1 1 10 1 1 1 12 1 1 1 1 6 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 9 1 1 1 1 11 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 2 1 1 1 1 1 1 12 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 6 1 1 1 1 1 1 1 1 1 1 1 ...

output:

10

result:

ok single line: '10'

Test #79:

score: 26
Accepted
time: 25ms
memory: 15012kb

input:

500000
9 2 2 1 9 1 12 1 5 1 15 2 4 1 1 1 14 1 11 1 11 1 11 1 9 1 6 1 13 1 4 1 9 1 5 1 9 1 14 1 1 2 10 1 8 1 2 1 9 1 5 1 6 1 3 1 15 1 2 1 8 2 4 1 3 1 2 1 2 1 5 2 14 1 1 1 7 1 4 1 6 1 5 1 8 1 14 1 12 1 9 1 8 1 11 1 8 2 8 1 8 1 3 1 14 1 9 1 12 1 12 1 12 1 11 1 13 1 3 1 6 1 4 1 3 1 5 1 10 1 8 1 8 2 7 2 ...

output:

13

result:

ok single line: '13'

Test #80:

score: 26
Accepted
time: 31ms
memory: 16896kb

input:

500000
4 1 8 1 2 1 11 1 9 1 3 1 14 2 1 1 9 1 11 1 4 1 13 1 8 1 15 1 8 1 13 1 15 1 12 1 9 1 12 1 13 1 1 1 11 1 8 1 14 1 8 1 14 1 5 1 6 1 4 1 5 1 7 1 3 1 9 1 5 1 15 1 1 1 12 1 2 1 9 1 3 1 11 1 4 1 5 1 14 1 14 1 9 1 2 1 8 1 9 1 7 1 8 1 2 1 14 1 8 1 11 1 6 1 15 1 4 1 2 1 12 1 9 1 15 1 5 1 6 1 1 1 2 1 14...

output:

10

result:

ok single line: '10'

Test #81:

score: 26
Accepted
time: 25ms
memory: 14896kb

input:

500000
14 2 8 1 1 1 8 1 3 1 11 1 15 1 11 2 7 2 11 1 15 1 11 1 1 2 11 1 10 1 10 1 5 1 12 1 2 1 2 3 2 1 6 1 9 1 7 1 8 1 8 1 4 2 8 3 14 1 6 1 6 1 9 1 7 1 5 2 2 1 13 1 6 1 5 4 12 3 5 1 3 1 5 1 6 1 8 1 13 1 11 1 13 1 3 1 4 2 1 1 12 2 12 2 7 1 2 1 4 1 12 1 11 2 6 3 6 1 11 1 10 1 6 1 4 1 3 1 3 1 11 1 3 1 4...

output:

15

result:

ok single line: '15'

Test #82:

score: 26
Accepted
time: 22ms
memory: 17048kb

input:

500000
15 15 15 14 13 15 15 15 15 15 13 15 15 15 15 15 14 15 14 15 15 13 15 15 14 15 13 15 15 15 14 15 13 13 15 14 15 15 15 15 14 15 15 14 13 15 15 15 15 15 15 13 15 14 14 15 13 15 15 15 15 15 15 13 14 15 15 15 15 13 14 13 15 14 14 15 15 15 15 13 14 15 15 14 15 15 15 13 15 15 15 13 13 14 15 15 14 15...

output:

15

result:

ok single line: '15'

Test #83:

score: 26
Accepted
time: 22ms
memory: 14880kb

input:

500000
8 7 11 7 7 6 7 13 7 11 2 7 7 7 11 15 13 11 9 3 4 5 7 7 9 11 7 7 5 4 8 7 7 7 7 2 12 13 5 1 4 4 7 7 4 14 5 7 7 7 6 4 1 8 10 13 7 7 7 7 15 7 9 6 4 9 15 7 5 7 3 7 7 4 7 7 11 6 8 6 7 7 7 7 3 7 1 10 2 7 6 7 11 7 7 8 4 5 15 11 7 15 7 7 11 2 9 7 14 7 6 7 7 1 4 7 14 6 7 7 1 2 1 7 7 13 7 1 7 6 15 7 9 6...

output:

15

result:

ok single line: '15'

Test #84:

score: 26
Accepted
time: 22ms
memory: 16884kb

input:

500000
2 2 2 2 4 2 2 2 1 1 2 2 2 2 2 2 6 2 10 11 2 10 2 2 2 2 2 11 2 2 11 15 2 2 2 5 2 7 2 2 2 2 10 2 12 2 2 2 2 2 2 2 2 2 2 2 2 2 2 11 2 2 2 2 9 2 2 2 15 2 1 2 2 2 2 2 2 2 2 5 3 8 2 2 2 2 2 2 2 2 11 2 2 2 2 2 2 2 13 2 2 2 2 2 2 2 2 9 2 2 12 2 15 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:

15

result:

ok single line: '15'

Test #85:

score: 26
Accepted
time: 25ms
memory: 17064kb

input:

500000
13 1 13 1 1 13 13 13 1 1 13 13 13 1 13 1 1 1 1 1 13 13 4 13 1 13 1 13 13 1 13 1 13 3 13 1 10 13 13 13 13 1 1 1 13 13 1 11 1 1 13 13 1 1 1 13 5 13 1 13 1 13 13 13 1 13 1 13 1 1 1 1 7 13 1 1 8 1 1 13 13 13 9 13 13 13 13 1 1 1 1 1 1 13 1 1 1 13 13 1 15 13 1 13 3 13 13 13 13 6 2 13 13 13 13 1 13 ...

output:

15

result:

ok single line: '15'

Test #86:

score: 26
Accepted
time: 19ms
memory: 14984kb

input:

499995
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

1

result:

ok single line: '1'

Test #87:

score: 26
Accepted
time: 22ms
memory: 16712kb

input:

499995
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15...

output:

15

result:

ok single line: '15'

Test #88:

score: 26
Accepted
time: 21ms
memory: 14856kb

input:

500000
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15...

output:

1

result:

ok single line: '1'

Test #89:

score: 26
Accepted
time: 28ms
memory: 17020kb

input:

500000
4 1 9 1 9 1 10 1 10 1 4 1 15 1 4 1 6 1 14 1 2 1 1 1 13 1 10 1 1 1 4 1 12 1 2 1 14 1 10 1 8 1 13 1 10 1 15 1 14 1 2 1 8 1 5 1 3 1 4 1 9 1 6 1 15 1 9 1 3 1 15 1 3 1 13 1 9 1 13 1 14 1 14 1 8 1 12 1 11 1 10 1 3 1 4 1 1 2 12 1 11 1 3 1 11 1 6 1 4 1 7 1 13 1 13 1 8 1 14 1 12 1 6 1 4 1 15 1 2 1 7 1...

output:

12

result:

ok single line: '12'

Test #90:

score: 26
Accepted
time: 28ms
memory: 14940kb

input:

500000
14 1 6 2 6 1 8 1 11 1 14 1 1 1 8 1 15 1 12 1 14 1 13 2 12 1 1 1 6 1 9 1 15 1 4 1 2 1 12 2 7 1 2 1 8 2 4 1 13 2 14 2 14 1 10 1 14 1 3 1 2 1 14 1 6 1 1 2 13 1 8 1 10 1 2 1 11 1 14 1 6 1 4 2 7 1 10 1 15 1 7 1 8 1 1 1 4 1 12 1 13 1 13 1 1 1 8 1 12 1 7 2 10 1 3 1 3 1 12 1 8 2 11 1 4 1 1 1 14 1 15 ...

output:

13

result:

ok single line: '13'

Test #91:

score: 26
Accepted
time: 224ms
memory: 17036kb

input:

500000
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15...

output:

14

result:

ok single line: '14'

Test #92:

score: 26
Accepted
time: 225ms
memory: 14964kb

input:

500000
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15...

output:

12

result:

ok single line: '12'

Subtask #6:

score: 0
Time Limit Exceeded

Test #93:

score: 10
Accepted
time: 36ms
memory: 14756kb

input:

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

output:

21

result:

ok single line: '21'

Test #94:

score: 10
Accepted
time: 44ms
memory: 14992kb

input:

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

output:

21

result:

ok single line: '21'

Test #95:

score: 10
Accepted
time: 23ms
memory: 16920kb

input:

500000
1 1 1 14 1 1 14 1 1 1 1 1 1 1 1 1 1 12 1 1 1 1 13 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 1 1 1 12 1 1 1 1 1 1 1 1 1 5 1 1 1 20 1 1 1 1 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 17 1 3 1 1 1 1 13 1 1 1 1 1 17 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 19 1 5 1 1 11 1 1 1 1 1 15 1 16 1 1 1 8 1 1 17 1 1 1 20 1 1 1 1 1 1...

output:

1

result:

ok single line: '1'

Test #96:

score: 10
Accepted
time: 50ms
memory: 14940kb

input:

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

output:

1

result:

ok single line: '1'

Test #97:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #7:

score: 0
Time Limit Exceeded

Test #122:

score: 18
Accepted
time: 227ms
memory: 31360kb

input:

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

output:

21

result:

ok single line: '21'

Test #123:

score: 18
Accepted
time: 224ms
memory: 31200kb

input:

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

output:

21

result:

ok single line: '21'

Test #124:

score: 18
Accepted
time: 242ms
memory: 31224kb

input:

5000000
1 1 1 1 1 1 9 1 1 7 1 8 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 11 1 1 1 1 1 1 1 17 1 14 1 1 1 4 1 1 1 11 1 1 20 1 14 1 1 1 1 1 1 1 6 1 1 1 1 1 21 1 1 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 8 1 1 1 1 1 1 19 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 15 1 1 11 1 1 1 7 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1

result:

ok single line: '1'

Test #125:

score: 18
Accepted
time: 1052ms
memory: 31300kb

input:

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

output:

1

result:

ok single line: '1'

Test #126:

score: 0
Time Limit Exceeded

input:

5000000
18 1 8 1 1 1 20 1 10 1 1 1 1 21 1 17 1 1 15 1 14 1 1 1 1 9 1 2 1 8 1 10 1 4 1 14 1 1 1 14 1 9 1 11 1 4 1 5 1 1 1 1 11 1 13 1 1 14 1 1 1 2 1 7 1 1 1 1 1 1 1 2 1 1 4 1 15 1 1 1 19 1 12 1 19 1 1 2 1 18 1 11 1 1 14 1 15 1 4 1 9 1 13 1 8 1 21 1 2 1 14 1 1 4 1 10 1 1 1 1 5 1 14 1 20 1 3 1 5 1 21 1...

output:


result: