QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#765761#8267. Staring Contest_8_8_#54.087093 23ms12956kbC++204.5kb2024-11-20 15:12:112024-11-20 15:12:12

Judging History

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

  • [2024-11-20 15:12:12]
  • 评测
  • 测评结果:54.087093
  • 用时:23ms
  • 内存:12956kb
  • [2024-11-20 15:12:11]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1500  + 12;

const ll inf = (ll)1e18;

int c = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(123121);
int n, p, res[N], a[N];
bool loc = 0;
int mem[N][N];
int get(int i, int j) {
    if(mem[i][j] != -1) return mem[i][j];   
    c++;
    if(loc) return min(a[i], a[j]);
    cout << "? " << i << ' ' << j << endl;
    int x;
    cin >> x;
    return mem[i][j] = mem[j][i] = x;
}
void solve(vector<int> x) {

    if((int)x.size() <= 1) return;
    if((int)x.size() == 2) {
        int val = get(x[0], x[1]);
        res[x[0]] = res[x[1]] = val;
        return;
    }
    if((int)x.size() == 3) {
        int val = get(x[0], x[1]);
        int val1 = get(x[1], x[2]);
        if(val == val1) {
            res[x[1]] = val;
            solve({x[0], x[2]});
            return;
        } else {
            res[x[0]] = val;
            res[x[1]] = max(val, val1);
            res[x[2]] = val1;
        }
        return;
    }
    vector<array<int, 3>> f;
    vector<int> y;
    vector<int> vis(n + 1, 0);
    while(!x.empty()) {
        int j = x.back();
        x.pop_back();
        if(vis[j]) continue;
        bool ok = 0;
        for(int r = 0; r < (int)x.size() - 1; r++) {
            if(mem[x[r]][j] != -1) {
                f.push_back({get(x[r], j), x[r], j});
                vis[x[r]] = 1;
                ok = 1;
                break;
            }
        }
        if(!ok) {
            y.push_back(j);
        }
    }
    x = y;
    int m = (int)x.size();
    vector<int> nx;
    if(m & 1) {
        x.pop_back();
    }
    m--;
    for(int i = 0; i < m; i += 2) {
        if(rng()%2) f.push_back({get(x[i], x[i + 1]), x[i], x[i + 1]});
        else f.push_back({get(x[i], x[i + 1]), x[i + 1], x[i]});;
    }
    sort(f.begin(), f.end());
    array<int, 3> bf = f.back();
    f.pop_back();
    while(!f.empty()) {
        array<int, 3> nv = f.back();
        f.pop_back();
        int val = get(nv[1], bf[1]);
        if(val == nv[0]) {
            res[nv[1]] = val;
        } else if(val == bf[0]) {
            res[bf[1]] = val;
            bf = nv;
        } else {    
            if(val > max(nv[0], bf[0])) {
                res[nv[2]] = nv[0];
                res[bf[2]] = bf[0];
                if(f.size() > 1) {
                    bf = f.back();
                    f.pop_back();
                    continue;
                }
            }
            if(nv[0] < bf[0]) res[nv[2]] = nv[0];
            else{
                res[bf[2]] = bf[0];
                bf = nv;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!res[i]) {
            nx.push_back(i);
        }
    }
    // assert((int)nx.size() <= (int)x.size() / 2 + 2);
    solve(nx);
}
bool check() {
    int c = 0;
    for(int i = 1; i <= n; i++) {
        if(res[i] > a[i]) return false;
        if(res[i] < a[i]) c++;
    }
    return (c <= 1);
}
bool str = 0;
void test() {
    memset(mem, -1, sizeof(mem));
    for(int i = 1; i <= n; i++) {
        res[i] = 0;
    }
    if(!str) {
        cin >> n;
        if(loc) {
            for(int i = 1; i <= n; i++) {
                cin >> a[i];
            }
        }
    }
    vector<int> f(n);
    iota(f.begin(), f.end(), 1);
    shuffle(f.begin(), f.end(), rng);
    solve(f);
    int mx = 0;
    for(int i = 1; i <= n; i++) {
        mx = max(mx ,res[i]);
    }
    for(int i =1; i <= n; i++) {
        if(!res[i]) res[i] = mx;
    }
    if(!str) {
        cout << "! ";
        for(int i = 1; i <= n; i++) {
            cout << res[i] << ' ';
        }
    }
}

void stress() {
    loc = str = 1;
    for(int i = 1; i <= 100; i++) {
        n = 1500;
        for(int j = 1; j <= n; j++) {
            a[j] = j;
        }
        shuffle(a + 1, a + n + 1, rng);
        c = 0;
        test();
        cout << c << '\n';
        if(!check()) {
            for(int j = 1; j <= n; j++) {
                cout << a[j] << ' ';
            }
            cout << '\n';
            for(int j = 1; j <= n; j++) {
                cout << res[j] << ' ';
            }
            cout << '\n';
            exit(0);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
        // stress();
        // return 0;
    int t = 1;
    // cin >> t;

    while(t--) 
        test();

    return 0;
}

详细

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 2ms
memory: 12568kb

input:

2
1

output:

? 2 1
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #2:

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

input:

2
1

output:

? 1 2
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #3:

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

input:

2
1

output:

? 2 1
! 1 1 

result:

points 1.0 points  1.0 n = 2, you used 1 queries

Test #4:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 86 queries

Test #5:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 68 queries

Test #6:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 74 queries

Test #7:

score: 9
Accepted
time: 3ms
memory: 12576kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 78 queries

Test #8:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 82 queries

Test #9:

score: 9
Accepted
time: 2ms
memory: 12604kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 77 queries

Test #10:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 78 queries

Test #11:

score: 9
Accepted
time: 3ms
memory: 12816kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 72 queries

Test #12:

score: 9
Accepted
time: 1ms
memory: 12636kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 80 queries

Test #13:

score: 9
Accepted
time: 3ms
memory: 12572kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 72 queries

Test #14:

score: 9
Accepted
time: 2ms
memory: 12736kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 74 queries

Test #15:

score: 9
Accepted
time: 3ms
memory: 12504kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 10, you used 13 queries

Test #16:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 10, you used 14 queries

Test #17:

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

input:

50
90
57
33
10
84
38
58
35
8
17
54
70
67
14
18
45
59
7
9
62
15
19
76
11
55
90
80
70
67
93
59
72
54
45
38
35
44
19
55
53
14
11
10
15
29
7
96
91
86
80
77
68
49
40
93
95
87
82
79
72
71
53
49
44
29
99
95
82
74
65
32
95
87
79
71
44
64
96
79
79
71
64
87
97
97

output:

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

result:

points 1.0 points  1.0 n = 50, you used 85 queries

Test #18:

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

input:

50
86363
86368
86356
86382
86355
86353
86354
86370
86381
86358
86361
86350
86388
86360
86359
86357
86351
86375
86372
86367
86373
86383
86369
86352
86385
86385
86383
86382
86381
86377
86373
86372
86370
86376
86386
86388
86363
86362
86360
86359
86378
86357
86379
86353
86366
86350
86398
86396
86393
863...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 87 queries

Test #19:

score: 9
Accepted
time: 3ms
memory: 12804kb

input:

50
5302
6651
5454
9654
8006
6297
6767
5076
7233
5914
6375
5813
9032
6824
5703
6476
7060
6109
7993
5406
7560
7159
8098
6099
8428
9032
9491
8947
8006
7993
7560
7233
8883
8060
6926
7779
6651
9654
7663
6109
6099
5914
5813
7026
5454
8464
5076
9732
9491
9258
8939
8883
8198
8060
7563
6926
9491
9404
8939
89...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 86 queries

Test #20:

score: 9
Accepted
time: 3ms
memory: 12548kb

input:

50
5029
5058
5051
5064
5023
5000
5048
5075
5036
5073
5004
5010
5068
5035
5066
5033
5021
5050
5005
5003
5049
5024
5017
5031
5039
5073
5068
5072
5075
5065
5076
5082
5038
5035
5039
5031
5029
5024
5023
5021
5059
5005
5004
5003
5010
5088
5084
5078
5069
5052
5041
5030
5025
5086
5082
5081
5076
5069
5065
50...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 86 queries

Test #21:

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

input:

50
67305
56501
62431
65062
53250
52391
58019
67289
50293
68114
58109
52428
57364
66780
61154
54556
75331
52604
66090
67638
70252
50918
74688
56134
51290
80336
76687
67305
67638
70891
65062
66090
61154
73709
58019
56501
69824
53250
54556
52428
52391
57154
50293
84732
80975
77305
72805
60767
54962
843...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 81 queries

Test #22:

score: 9
Accepted
time: 3ms
memory: 12576kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 80 queries

Test #23:

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

input:

50
55
66
94
14
11
38
5
41
6
29
95
15
10
26
25
3
36
49
20
9
58
73
7
2
69
95
73
69
66
97
49
41
52
36
29
55
31
15
14
20
10
9
46
5
39
2
96
70
68
67
52
78
17
79
46
96
79
78
75
68
67
52
86
39
90
72
80
56
89
72
86
89
80
98
72
88
56
42
88
90
42
56
91
56
91
85
85
98

output:

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

result:

points 1.0 points  1.0 n = 50, you used 88 queries

Test #24:

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

input:

50
86361
86383
86382
86351
86367
86352
86355
86376
86394
86353
86365
86356
86354
86377
86384
86350
86364
86385
86371
86366
86374
86359
86362
86373
86358
86385
86384
86383
86382
86377
86389
86375
86373
86390
86367
86378
86379
86364
86387
86388
86359
86381
86369
86386
86363
86392
86352
86370
86350
863...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 78 queries

Test #25:

score: 9
Accepted
time: 1ms
memory: 12632kb

input:

50
6181
7541
9055
6461
6786
6553
5141
8197
7829
5503
5144
5118
6327
5907
6722
7405
7115
5271
5529
7509
6205
5252
5310
5171
5603
8197
8135
7553
9184
7115
7960
6553
6850
6205
6181
6327
5603
5529
6051
5271
5299
5310
7036
5141
6856
7553
6725
6614
9184
7215
5299
8135
8722
7553
7215
7036
6856
6850
7205
66...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 83 queries

Test #26:

score: 9
Accepted
time: 3ms
memory: 12568kb

input:

50
5088
5065
5076
5049
5012
5027
5032
5007
5014
5001
5073
5005
5019
5028
5086
5010
5013
5009
5045
5002
5011
5052
5029
5033
5047
5088
5076
5073
5065
5095
5049
5063
5044
5054
5042
5013
5025
5056
5009
5059
5024
5051
5039
5087
5087
5078
5062
5071
5054
5051
5044
5042
5089
5058
5024
5046
5074
5035
5058
50...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 73 queries

Test #27:

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

input:

50
58717
65477
75023
62248
68422
61968
57318
66448
71272
70928
67146
53987
54250
76101
53454
61401
79047
75075
55504
53213
51658
58746
73863
74083
58357
76101
79047
75023
76671
71272
70928
68422
67146
66448
72987
73863
77213
70576
58357
72291
62990
74971
54630
81101
79827
78154
72620
67069
81101
804...

output:

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

result:

points 1.0 points  1.0 n = 50, you used 74 queries

Test #28:

score: 9
Accepted
time: 4ms
memory: 12516kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 75 queries

Test #29:

score: 9
Accepted
time: 3ms
memory: 12496kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 75 queries

Test #30:

score: 9
Accepted
time: 3ms
memory: 12640kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 76 queries

Test #31:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 83 queries

Test #32:

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

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 89 queries

Test #33:

score: 9
Accepted
time: 1ms
memory: 12560kb

input:

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

output:

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

result:

points 1.0 points  1.0 n = 50, you used 77 queries

Test #34:

score: 9
Accepted
time: 3ms
memory: 12564kb

input:

4
2
5
2
3

output:

? 1 2
? 4 3
? 1 4
? 2 3
! 2 3 5 5 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #35:

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

input:

4
2
5
3
3

output:

? 1 2
? 4 3
? 2 4
? 2 3
! 2 3 5 5 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #36:

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

input:

4
5
2
2
3
3

output:

? 4 2
? 1 3
? 1 2
? 2 3
? 3 4
! 2 5 3 5 

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #37:

score: 9
Accepted
time: 2ms
memory: 12556kb

input:

4
5
2
3
3

output:

? 2 3
? 4 1
? 4 2
? 3 4
! 2 5 5 3 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #38:

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

input:

4
5
2
3
3

output:

? 2 4
? 3 1
? 3 2
? 3 4
! 2 5 3 5 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #39:

score: 9
Accepted
time: 2ms
memory: 12800kb

input:

4
2
3
3
2
5

output:

? 1 3
? 4 2
? 3 4
? 1 2
? 2 3
! 2 5 5 3 

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #40:

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

input:

4
2
3
5

output:

? 2 3
? 1 4
? 3 4
! 3 2 5 5 

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #41:

score: 9
Accepted
time: 3ms
memory: 12636kb

input:

4
5
2
2
3

output:

? 3 4
? 1 2
? 2 3
? 1 3
! 3 2 5 5 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #42:

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

input:

4
5
2
2
3

output:

? 2 4
? 1 3
? 3 4
? 1 2
! 3 5 2 5 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #43:

score: 9
Accepted
time: 2ms
memory: 12524kb

input:

4
3
2
5

output:

? 3 1
? 2 4
? 2 3
! 3 5 5 2 

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #44:

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

input:

4
2
3
2
3
5

output:

? 2 3
? 4 1
? 3 4
? 1 2
? 2 4
! 3 5 2 5 

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #45:

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

input:

4
2
3
2
5

output:

? 4 3
? 2 1
? 4 2
? 2 3
! 3 5 5 2 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #46:

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

input:

4
2
5
2
3
3

output:

? 2 3
? 4 1
? 2 4
? 1 3
? 3 4
! 5 2 3 5 

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #47:

score: 9
Accepted
time: 3ms
memory: 12568kb

input:

4
3
2
2
5

output:

? 4 3
? 2 1
? 2 4
? 1 3
! 5 2 5 3 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #48:

score: 9
Accepted
time: 2ms
memory: 12540kb

input:

4
2
5
3
3

output:

? 2 3
? 4 1
? 2 4
? 1 2
! 5 3 2 5 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #49:

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

input:

4
2
5
3
3

output:

? 2 4
? 1 3
? 2 1
? 2 3
! 5 3 5 2 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #50:

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

input:

4
2
3
3
5
2

output:

? 1 3
? 2 4
? 1 4
? 1 2
? 2 3
! 5 5 2 3 

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #51:

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

input:

4
2
5
2
3

output:

? 4 3
? 2 1
? 4 2
? 2 3
! 5 5 3 2 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #52:

score: 9
Accepted
time: 3ms
memory: 12572kb

input:

4
5
2
3
3

output:

? 4 1
? 2 3
? 3 1
? 3 4
! 5 2 3 5 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #53:

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

input:

4
3
2
5

output:

? 3 4
? 2 1
? 1 3
! 5 2 5 3 

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #54:

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

input:

4
3
2
5

output:

? 4 2
? 1 3
? 1 4
! 5 3 2 5 

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Test #55:

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

input:

4
2
3
2
3
5

output:

? 4 3
? 1 2
? 4 2
? 2 3
? 1 3
! 5 3 5 2 

result:

points 1.0 points  1.0 n = 4, you used 5 queries

Test #56:

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

input:

4
2
3
2
5

output:

? 1 3
? 4 2
? 3 4
? 1 2
! 5 5 2 3 

result:

points 1.0 points  1.0 n = 4, you used 4 queries

Test #57:

score: 9
Accepted
time: 2ms
memory: 12628kb

input:

4
5
2
3

output:

? 2 1
? 3 4
? 3 2
! 5 5 3 2 

result:

points 1.0 points  1.0 n = 4, you used 3 queries

Subtask #2:

score: 11
Accepted

Test #58:

score: 11
Accepted
time: 4ms
memory: 12724kb

input:

1000
579
201
365
23
107
533
662
329
372
138
135
632
55
441
885
777
65
25
469
813
429
805
3
818
525
10
81
28
637
255
256
414
589
841
47
497
674
128
684
351
73
337
289
308
595
14
551
92
447
367
131
275
239
370
145
719
487
306
152
598
270
142
293
251
196
99
645
633
470
282
556
104
606
154
30
194
122
13...

output:

? 823 579
? 618 201
? 865 365
? 23 573
? 522 107
? 927 533
? 771 662
? 806 329
? 502 372
? 138 629
? 135 507
? 632 668
? 985 55
? 441 749
? 885 929
? 777 936
? 405 65
? 565 25
? 469 687
? 864 813
? 429 488
? 831 805
? 694 3
? 818 884
? 526 525
? 10 975
? 837 81
? 963 28
? 892 637
? 425 255
? 256 710...

result:

points 1.0 points  1.0 n = 1000, you used 1711 queries

Test #59:

score: 11
Accepted
time: 0ms
memory: 12632kb

input:

1000
12
934
211
571
761
85
246
236
226
597
491
110
93
192
372
161
356
54
487
306
190
157
784
319
18
232
117
628
824
237
248
95
402
663
175
682
802
526
94
964
427
172
829
512
147
141
144
52
21
502
426
403
450
339
184
171
492
508
334
396
260
111
694
976
671
133
701
916
272
182
252
44
185
87
483
440
45...

output:

? 989 627
? 67 41
? 455 790
? 410 430
? 108 240
? 35 916
? 755 340
? 765 106
? 775 416
? 226 404
? 334 510
? 163 891
? 11 908
? 809 202
? 323 629
? 840 165
? 645 466
? 947 878
? 514 2
? 666 695
? 560 811
? 571 844
? 185 217
? 682 414
? 768 983
? 769 137
? 884 650
? 267 373
? 177 31
? 291 764
? 324 7...

result:

points 1.0 points  1.0 n = 1000, you used 1367 queries

Test #60:

score: 11
Accepted
time: 10ms
memory: 12584kb

input:

1000
781
474
334
119
278
275
442
34
255
352
561
524
40
455
516
336
256
840
1
341
814
232
316
21
579
195
720
252
93
432
298
534
362
211
117
408
613
200
56
115
12
646
453
163
143
331
180
658
310
168
75
170
399
406
196
263
4
123
116
372
443
50
556
87
688
888
794
206
462
451
185
291
508
47
393
515
461
1...

output:

? 391 478
? 764 526
? 834 234
? 577 60
? 862 561
? 138 390
? 397 780
? 323 984
? 128 490
? 825 273
? 281 534
? 739 344
? 399 981
? 547 228
? 708 743
? 263 833
? 700 873
? 456 581
? 335 1
? 760 171
? 426 594
? 400 885
? 251 843
? 11 12
? 290 405
? 493 98
? 520 641
? 694 875
? 948 47
? 380 785
? 852 7...

result:

points 1.0 points  1.0 n = 1000, you used 1575 queries

Test #61:

score: 11
Accepted
time: 0ms
memory: 12708kb

input:

1000
406
156
752
44
113
61
22
845
627
283
269
190
247
817
34
396
458
256
424
374
95
32
145
744
108
354
137
277
291
253
107
189
164
201
87
574
230
715
346
644
123
514
371
196
281
43
453
692
126
52
426
51
439
369
60
375
204
90
871
120
276
168
321
665
5
450
297
576
257
249
716
264
610
133
21
98
318
298...

output:

? 203 563
? 509 78
? 376 533
? 22 59
? 441 944
? 637 970
? 913 11
? 457 578
? 687 413
? 859 471
? 670 866
? 239 95
? 877 335
? 592 414
? 614 17
? 437 198
? 444 229
? 128 150
? 591 212
? 620 187
? 802 953
? 16 908
? 928 281
? 396 372
? 54 336
? 177 711
? 715 932
? 862 663
? 244 855
? 532 874
? 427 94...

result:

points 1.0 points  1.0 n = 1000, you used 1526 queries

Test #62:

score: 11
Accepted
time: 3ms
memory: 12840kb

input:

1000
160
893
234
602
514
307
209
117
215
297
842
35
30
175
684
592
635
94
425
90
213
678
191
36
20
597
97
744
332
77
579
794
441
82
631
142
253
378
159
225
815
391
10
716
124
516
88
60
529
13
7
12
192
39
599
430
113
227
73
470
153
139
581
764
164
23
108
686
206
1
302
343
81
72
440
452
245
633
751
27...

output:

? 957 421
? 947 964
? 141 384
? 200 101
? 244 44
? 97 654
? 605 981
? 559 575
? 738 608
? 649 700
? 924 80
? 518 574
? 772 486
? 412 588
? 159 109
? 205 986
? 818 833
? 454 741
? 713 180
? 216 456
? 191 607
? 162 865
? 796 596
? 533 483
? 276 491
? 799 808
? 549 925
? 20 129
? 335 838
? 539 320
? 20...

result:

points 1.0 points  1.0 n = 1000, you used 1491 queries

Test #63:

score: 11
Accepted
time: 9ms
memory: 12580kb

input:

1000
862
231
274
149
239
27
313
116
745
262
654
681
716
361
67
335
163
196
711
319
29
549
444
38
585
165
330
215
384
233
512
537
208
657
99
324
865
435
425
652
7
353
279
411
374
481
539
909
253
758
108
519
660
688
183
41
717
802
180
329
801
31
538
221
337
323
469
606
214
664
515
161
190
427
248
448
...

output:

? 26 931
? 385 990
? 763 637
? 426 936
? 82 381
? 715 487
? 344 690
? 213 558
? 128 21
? 965 631
? 827 146
? 112 160
? 858 137
? 718 320
? 467 885
? 141 333
? 589 419
? 833 598
? 144 145
? 107 341
? 486 813
? 226 62
? 722 80
? 519 759
? 208 924
? 418 415
? 665 929
? 930 393
? 889 692
? 384 177
? 223...

result:

points 1.0 points  1.0 n = 1000, you used 1530 queries

Test #64:

score: 11
Accepted
time: 11ms
memory: 12912kb

input:

1000
11
138
444
178
384
314
357
562
255
229
297
284
814
214
115
96
296
235
641
396
824
79
369
242
21
184
762
882
137
48
264
756
548
42
621
204
379
865
89
362
482
353
355
615
2
323
248
35
949
342
144
651
122
315
231
433
200
261
272
17
62
130
509
49
59
20
337
878
97
171
516
3
726
570
348
34
198
114
45...

output:

? 566 979
? 644 725
? 464 113
? 645 934
? 900 233
? 315 373
? 287 53
? 368 124
? 138 491
? 543 361
? 180 407
? 433 72
? 820 628
? 814 573
? 771 347
? 734 809
? 290 409
? 489 531
? 282 490
? 838 209
? 910 648
? 320 843
? 263 164
? 880 517
? 959 916
? 738 633
? 524 570
? 836 764
? 467 727
? 383 905
? ...

result:

points 1.0 points  1.0 n = 1000, you used 1685 queries

Test #65:

score: 11
Accepted
time: 0ms
memory: 12676kb

input:

1000
547
304
46
672
15
354
11
102
392
470
613
140
202
820
472
705
490
856
47
459
687
702
23
630
272
309
161
619
282
718
120
20
620
479
589
503
780
433
466
376
182
215
294
229
722
249
351
225
35
168
131
397
62
81
130
488
12
314
135
77
827
625
86
293
137
79
152
505
263
280
655
61
201
166
485
200
260
1...

output:

? 261 907
? 608 917
? 92 192
? 657 399
? 573 30
? 708 961
? 22 475
? 769 204
? 784 355
? 940 471
? 463 775
? 280 369
? 175 404
? 281 361
? 821 944
? 539 591
? 375 980
? 289 49
? 963 94
? 918 993
? 161 627
? 121 597
? 46 515
? 623 741
? 544 505
? 618 650
? 987 322
? 651 763
? 885 564
? 95 565
? 771 2...

result:

points 1.0 points  1.0 n = 1000, you used 1421 queries

Test #66:

score: 11
Accepted
time: 4ms
memory: 12652kb

input:

1000
98
190
562
116
490
525
440
609
495
57
144
472
558
96
333
8
320
61
16
192
105
538
464
429
596
65
297
125
249
451
95
245
219
134
76
209
47
153
87
218
367
380
639
442
683
795
315
188
168
52
198
345
686
149
58
703
70
141
773
293
317
63
681
749
433
150
177
607
256
560
27
373
211
162
566
599
187
970
...

output:

? 99 622
? 477 191
? 563 949
? 117 295
? 491 966
? 699 524
? 811 441
? 968 608
? 987 494
? 695 56
? 145 484
? 473 710
? 559 658
? 97 989
? 332 489
? 569 9
? 993 321
? 215 60
? 662 17
? 220 193
? 104 377
? 539 589
? 465 731
? 729 428
? 741 597
? 64 536
? 837 296
? 124 331
? 248 612
? 450 694
? 346 94...

result:

points 1.0 points  1.0 n = 1000, you used 1702 queries

Test #67:

score: 11
Accepted
time: 0ms
memory: 12812kb

input:

1000
281
215
30
41
155
2
256
424
655
211
323
227
290
861
100
50
669
82
544
123
79
111
818
358
736
242
728
435
546
694
299
283
275
846
664
702
517
58
187
198
477
578
34
70
452
421
441
340
7
241
95
812
568
368
600
172
848
76
596
231
276
661
403
333
104
735
265
289
580
297
493
751
22
681
259
464
209
14...

output:

? 284 721
? 787 412
? 970 171
? 733 961
? 847 392
? 998 129
? 458 744
? 576 314
? 11 347
? 791 180
? 102 679
? 470 775
? 384 710
? 141 8
? 131 900
? 846 950
? 333 128
? 781 918
? 456 82
? 589 879
? 413 923
? 512 891
? 173 182
? 110 642
? 264 59
? 175 758
? 67 272
? 567 479
? 42 454
? 109 306
? 62 70...

result:

points 1.0 points  1.0 n = 1000, you used 1349 queries

Test #68:

score: 11
Accepted
time: 0ms
memory: 12540kb

input:

300
216
223
1
193
146
24
31
7
149
205
4
82
126
58
34
140
111
47
151
254
195
247
122
164
215
72
198
78
39
62
40
48
51
104
85
181
9
11
42
77
65
103
143
84
250
13
20
134
89
101
66
137
169
52
2
141
15
19
50
133
116
135
121
57
161
81
28
14
138
258
90
178
23
136
184
166
56
153
44
114
251
55
63
273
10
261
...

output:

? 216 259
? 223 240
? 144 1
? 265 193
? 208 146
? 299 24
? 31 219
? 275 7
? 149 200
? 243 205
? 4 120
? 82 210
? 176 126
? 152 58
? 115 34
? 217 140
? 263 111
? 99 47
? 151 188
? 254 257
? 264 195
? 247 281
? 190 122
? 164 253
? 290 215
? 177 72
? 198 232
? 80 78
? 39 64
? 62 158
? 276 40
? 129 48
?...

result:

points 1.0 points  1.0 n = 300, you used 518 queries

Test #69:

score: 11
Accepted
time: 5ms
memory: 12564kb

input:

300
143
19
15
125
162
220
111
78
6
236
20
61
226
45
10
76
103
31
50
36
32
14
229
42
52
84
129
4
72
8
54
3
262
187
43
216
1
238
102
160
101
26
232
219
146
112
173
212
27
65
58
153
131
167
218
12
183
51
49
82
41
73
68
140
56
96
97
46
116
11
161
13
18
38
223
23
80
48
224
37
57
69
91
227
25
81
148
94
15...

output:

? 272 283
? 148 281
? 72 246
? 282 118
? 224 162
? 260 44
? 203 179
? 184 95
? 128 84
? 149 213
? 104 233
? 223 54
? 107 187
? 145 167
? 251 297
? 244 219
? 66 55
? 156 255
? 22 75
? 186 133
? 16 42
? 147 64
? 43 15
? 208 114
? 30 161
? 7 288
? 99 117
? 222 2
? 299 37
? 70 101
? 63 18
? 188 249
? 29...

result:

points 1.0 points  1.0 n = 300, you used 447 queries

Test #70:

score: 11
Accepted
time: 13ms
memory: 12640kb

input:

1000
90
176
115
842
392
196
311
282
352
219
600
394
135
187
459
765
140
790
772
15
353
96
456
246
544
548
414
113
12
30
103
763
339
144
598
452
154
371
335
163
796
332
453
49
366
307
251
249
458
64
826
116
165
886
491
471
429
673
638
61
475
254
45
358
552
270
276
463
314
123
221
492
36
427
170
19
29...

output:

? 815 277
? 163 552
? 44 875
? 191 543
? 328 902
? 285 758
? 864 514
? 708 85
? 487 3
? 292 406
? 77 677
? 877 916
? 551 643
? 599 287
? 838 811
? 366 434
? 754 474
? 159 720
? 555 386
? 1 398
? 834 597
? 874 58
? 199 23
? 78 889
? 530 993
? 522 999
? 29 310
? 785 953
? 532 414
? 368 463
? 215 377
?...

result:

points 1.0 points  1.0 n = 1000, you used 1526 queries

Test #71:

score: 11
Accepted
time: 0ms
memory: 12648kb

input:

1000
463
452
23
833
916
201
1114
777
402
241
56
979
1409
586
195
851
1337
945
345
1672
371
57
248
608
314
417
902
1567
748
204
207
621
1000
42
246
90
1117
1450
295
788
82
397
349
858
20
942
7
528
919
1029
545
231
318
1111
536
791
48
1713
1177
254
702
70
665
755
894
944
428
736
25
1085
709
1253
1077
...

output:

? 241 671
? 879 237
? 77 16
? 429 700
? 472 853
? 102 592
? 881 572
? 399 906
? 210 276
? 128 611
? 139 35
? 504 502
? 930 717
? 637 304
? 138 99
? 436 452
? 678 891
? 831 485
? 180 899
? 907 836
? 194 814
? 723 36
? 132 533
? 569 318
? 359 162
? 217 698
? 467 985
? 928 794
? 386 430
? 801 104
? 107...

result:

points 1.0 points  1.0 n = 1000, you used 1694 queries

Test #72:

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

input:

1000
85650
86098
85571
85620
85600
85534
85677
85452
85475
86050
85624
85898
85420
85961
85685
85467
85949
86172
85451
85545
85651
86171
85867
85642
85505
85626
86102
85555
85584
86146
85595
85585
85764
86138
86078
85905
85950
85659
85670
85594
86128
86082
85895
85715
85606
85853
85730
86015
85696
8...

output:

? 251 775
? 760 698
? 642 172
? 659 221
? 201 867
? 135 412
? 278 342
? 53 620
? 396 76
? 764 650
? 225 510
? 499 711
? 21 592
? 561 602
? 286 951
? 68 989
? 556 549
? 772 937
? 52 583
? 494 146
? 932 252
? 787 771
? 621 468
? 877 243
? 265 106
? 318 227
? 733 702
? 482 156
? 821 185
? 746 762
? 196...

result:

points 1.0 points  1.0 n = 1000, you used 1665 queries

Test #73:

score: 11
Accepted
time: 11ms
memory: 12660kb

input:

1000
5553
8335
5543
5448
6599
8494
7466
8565
5851
8871
8701
9215
5304
6348
7999
7203
8780
5775
5762
5299
8292
6985
6403
6935
6584
5258
6774
6481
7520
5847
8670
7163
6512
5901
5423
7059
7723
6522
6380
7813
8295
7458
5815
8067
6347
8266
8911
5889
5872
7658
8199
6592
8960
6235
5013
5407
6016
7026
6611
...

output:

? 382 93
? 915 647
? 89 570
? 281 75
? 297 282
? 969 682
? 610 456
? 957 697
? 142 558
? 786 764
? 832 726
? 948 840
? 462 48
? 442 234
? 573 750
? 582 409
? 743 767
? 133 660
? 130 208
? 298 46
? 849 636
? 396 365
? 439 246
? 626 351
? 552 279
? 40 210
? 509 317
? 264 518
? 469 887
? 141 426
? 909 ...

result:

points 1.0 points  1.0 n = 1000, you used 1724 queries

Test #74:

score: 11
Accepted
time: 9ms
memory: 12660kb

input:

1000
4123
5495
4388
4104
4188
4312
4389
4147
4686
4863
4204
4327
4610
4506
4964
5299
5043
4649
4202
4259
4744
4287
5688
5247
4061
4136
4088
4514
4221
4970
5049
4829
4137
5453
5262
4181
4117
4831
4826
4173
4633
4687
5195
4735
5717
4644
4056
4398
5061
5733
4750
4501
4194
5128
4048
4893
4494
4125
4465
...

output:

? 61 564
? 881 742
? 205 513
? 538 53
? 974 106
? 987 168
? 206 828
? 81 879
? 585 342
? 432 837
? 113 677
? 581 176
? 304 400
? 575 255
? 722 480
? 652 911
? 607 518
? 323 399
? 111 444
? 141 368
? 418 373
? 155 625
? 973 842
? 975 626
? 483 29
? 493 72
? 42 124
? 481 260
? 589 120
? 484 599
? 521 ...

result:

points 1.0 points  1.0 n = 1000, you used 1743 queries

Test #75:

score: 11
Accepted
time: 3ms
memory: 12848kb

input:

1000
71765
51353
75243
81446
56469
60568
65192
75540
55857
55718
65940
62142
69890
56704
66432
60367
65688
61075
60636
53792
60392
61305
60753
61033
64070
55475
71685
52548
66261
56301
73771
54631
69065
51909
50566
51199
60775
53791
53333
66512
58772
52812
58729
50881
70187
50185
74038
63071
60856
5...

output:

? 607 814
? 33 878
? 712 933
? 868 881
? 348 161
? 276 734
? 873 404
? 841 717
? 759 141
? 138 215
? 427 628
? 480 319
? 899 541
? 171 948
? 447 681
? 939 270
? 762 421
? 295 364
? 424 278
? 95 97
? 967 272
? 529 301
? 281 526
? 293 544
? 370 514
? 705 132
? 623 603
? 62 686
? 440 580
? 445 157
? 10...

result:

points 1.0 points  1.0 n = 1000, you used 1699 queries

Test #76:

score: 11
Accepted
time: 9ms
memory: 12620kb

input:

1000
737
636
789
537
455
229
136
705
110
343
201
9
14
29
493
562
532
94
946
370
564
504
52
396
784
86
602
225
485
624
374
569
48
496
600
23
83
882
499
608
137
281
417
442
310
775
35
143
139
473
200
420
168
256
164
428
457
147
525
393
265
102
447
422
309
341
419
214
166
613
368
220
605
76
752
115
158...

output:

? 771 865
? 6 815
? 799 502
? 945 184
? 166 616
? 730 824
? 702 197
? 889 327
? 265 499
? 1 531
? 779 762
? 814 438
? 767 637
? 639 230
? 538 388
? 631 659
? 757 246
? 364 618
? 34 89
? 692 651
? 561 628
? 359 117
? 596 93
? 11 179
? 460 201
? 399 427
? 363 894
? 501 68
? 678 294
? 341 119
? 242 940...

result:

points 1.0 points  1.0 n = 1000, you used 1553 queries

Test #77:

score: 11
Accepted
time: 7ms
memory: 12884kb

input:

1000
1187
626
1407
639
1192
646
1070
456
190
1409
6
83
1316
1035
861
831
89
888
100
505
1384
944
788
969
680
1622
70
521
1068
731
901
928
250
972
38
1167
1284
342
395
543
614
730
979
1810
536
135
279
1750
435
185
586
580
175
1492
588
657
111
1067
246
871
317
108
658
947
12
318
751
1403
1151
679
37
2...

output:

? 911 904
? 940 81
? 139 531
? 897 302
? 693 341
? 639 528
? 453 896
? 573 64
? 492 996
? 733 498
? 265 737
? 691 172
? 208 853
? 380 178
? 392 90
? 607 366
? 602 232
? 435 887
? 323 571
? 688 495
? 192 722
? 422 710
? 359 36
? 22 350
? 165 673
? 980 352
? 485 210
? 738 396
? 393 484
? 386 854
? 537...

result:

points 1.0 points  1.0 n = 1000, you used 1512 queries

Test #78:

score: 11
Accepted
time: 0ms
memory: 12716kb

input:

1000
86190
86209
85913
86203
85410
86208
85492
86282
86039
85653
85910
85507
85833
85543
85759
85417
85674
85610
85585
86072
86003
85407
85755
85789
85546
86130
85670
85584
85433
85963
85465
85975
85440
85478
85737
85631
85665
85416
85658
85930
85818
85772
85560
85845
85712
85996
85544
85980
85488
8...

output:

? 946 975
? 399 676
? 908 413
? 836 600
? 40 143
? 397 345
? 737 748
? 688 431
? 14 506
? 832 925
? 10 625
? 640 922
? 652 99
? 776 402
? 998 713
? 252 746
? 469 389
? 84 500
? 741 451
? 133 268
? 429 551
? 15 666
? 405 305
? 718 712
? 678 549
? 473 338
? 293 641
? 146 131
? 238 800
? 284 508
? 92 1...

result:

points 1.0 points  1.0 n = 1000, you used 1514 queries

Test #79:

score: 11
Accepted
time: 0ms
memory: 12832kb

input:

1000
7524
6042
8092
7448
8391
8508
7062
5458
6974
6614
5261
7908
6014
6755
5058
5184
6768
8632
7180
5189
8136
5968
6868
5053
7008
7938
6733
5566
6279
7572
6981
7270
8904
7283
6717
5158
5223
5249
8126
6177
6707
6457
8275
5897
7700
8461
8999
5446
6473
7632
5671
6017
6781
5925
5066
9483
5346
5530
5495
...

output:

? 566 46
? 741 496
? 124 850
? 980 313
? 498 447
? 998 428
? 23 852
? 335 330
? 215 382
? 884 457
? 577 568
? 798 190
? 173 149
? 104 893
? 764 342
? 154 228
? 157 289
? 29 119
? 413 855
? 724 92
? 507 151
? 295 661
? 555 13
? 58 881
? 689 666
? 920 822
? 85 948
? 381 155
? 833 751
? 366 169
? 4 217...

result:

points 1.0 points  1.0 n = 1000, you used 1515 queries

Test #80:

score: 11
Accepted
time: 0ms
memory: 12808kb

input:

1000
4291
4148
4929
4104
4453
5458
4507
4261
4194
4779
4106
4462
4035
4251
4948
5300
5500
4561
5137
5037
5118
4794
4078
4571
4519
4402
4673
4416
4103
4140
4175
5033
4088
4810
4297
4329
4070
5611
4721
4273
4257
5797
4201
5171
4366
4450
5000
4118
4857
4249
4544
4441
4280
5067
5483
4328
4218
4558
4504
...

output:

? 339 495
? 839 562
? 480 137
? 973 139
? 336 668
? 647 305
? 622 210
? 530 744
? 478 448
? 235 923
? 212 105
? 164 40
? 498 970
? 317 248
? 674 846
? 782 479
? 177 443
? 160 665
? 643 435
? 686 190
? 813 18
? 596 377
? 998 298
? 933 706
? 346 389
? 735 431
? 528 450
? 553 21
? 373 314
? 966 694
? 1...

result:

points 1.0 points  1.0 n = 1000, you used 1532 queries

Test #81:

score: 11
Accepted
time: 5ms
memory: 12616kb

input:

1000
63140
76370
59547
53368
54370
65015
50385
61705
67124
50304
68290
71190
80365
55453
70859
52949
54524
74864
54757
73365
50293
61439
56512
64316
65769
50618
76920
63509
50536
59862
54300
69905
51359
74181
62886
77453
59680
66530
56662
53572
53573
58690
75527
68715
58419
54535
55794
56542
65925
7...

output:

? 426 992
? 813 30
? 532 548
? 393 16
? 491 582
? 68 999
? 119 608
? 118 378
? 362 910
? 421 934
? 10 780
? 863 639
? 54 928
? 187 878
? 941 425
? 454 71
? 713 851
? 13 807
? 64 314
? 595 484
? 663 666
? 945 108
? 444 402
? 575 898
? 129 767
? 487 804
? 29 581
? 417 106
? 171 72
? 56 622
? 7 912
? 1...

result:

points 1.0 points  1.0 n = 1000, you used 1483 queries

Test #82:

score: 11
Accepted
time: 2ms
memory: 12548kb

input:

1000
282
779
51
149
158
274
114
144
428
499
438
195
698
461
333
473
379
621
556
376
467
298
350
12
248
81
852
192
185
689
76
232
41
5
717
667
189
26
19
130
393
536
459
694
433
757
132
311
287
160
708
291
184
180
483
869
103
432
392
426
707
292
328
271
361
225
66
75
680
403
301
54
637
295
181
656
722...

output:

? 282 342
? 779 781
? 437 51
? 149 795
? 314 158
? 274 909
? 337 114
? 144 387
? 752 428
? 593 499
? 696 438
? 627 195
? 900 698
? 778 461
? 333 867
? 940 473
? 379 676
? 621 630
? 710 556
? 962 376
? 467 761
? 551 298
? 350 972
? 391 12
? 590 248
? 140 81
? 942 852
? 192 683
? 981 185
? 756 689
? 3...

result:

points 1.0 points  1.0 n = 1000, you used 1721 queries

Test #83:

score: 11
Accepted
time: 6ms
memory: 12576kb

input:

1000
569
97
501
283
361
428
260
2
101
56
165
746
410
169
201
10
316
862
507
166
181
514
48
231
252
498
121
164
11
150
478
461
196
63
93
245
209
725
620
395
503
442
630
50
106
492
375
789
157
774
6
105
639
449
322
752
421
397
113
434
261
265
525
222
138
312
151
139
474
574
524
143
451
180
721
87
9
62...

output:

? 569 766
? 97 310
? 622 501
? 666 283
? 361 470
? 428 675
? 952 260
? 1000 489
? 300 101
? 56 699
? 178 165
? 874 746
? 685 410
? 880 169
? 696 201
? 10 171
? 316 796
? 862 949
? 704 507
? 166 537
? 565 181
? 723 514
? 114 48
? 640 231
? 641 252
? 498 980
? 121 791
? 164 604
? 877 11
? 150 560
? 52...

result:

points 1.0 points  1.0 n = 1000, you used 1568 queries

Test #84:

score: 11
Accepted
time: 4ms
memory: 12708kb

input:

1000
210
335
472
193
724
22
183
135
13
57
513
139
543
639
37
187
634
818
538
288
685
918
216
179
12
384
250
277
61
184
136
215
482
357
416
24
249
39
176
180
15
304
409
358
802
812
47
502
757
514
324
95
274
75
594
169
441
195
248
572
130
425
771
32
332
599
1
394
123
678
702
161
298
466
403
43
550
78
...

output:

? 15 531
? 506 42
? 234 199
? 656 655
? 301 707
? 861 888
? 145 671
? 176 576
? 291 323
? 946 321
? 414 438
? 346 535
? 619 512
? 370 130
? 844 104
? 713 185
? 952 788
? 509 549
? 916 905
? 914 331
? 290 160
? 775 900
? 111 704
? 60 798
? 66 279
? 118 565
? 590 339
? 157 277
? 747 752
? 814 732
? 43...

result:

points 1.0 points  1.0 n = 1000, you used 1633 queries

Test #85:

score: 11
Accepted
time: 0ms
memory: 12688kb

input:

1000
301
170
10
42
80
935
411
326
55
202
247
554
117
4
585
358
468
485
646
18
122
215
610
489
11
22
81
562
207
2
494
378
340
146
570
465
59
357
665
401
213
47
289
40
513
126
228
285
198
713
671
24
526
227
185
123
151
20
772
268
347
172
548
332
79
625
390
386
158
435
522
273
659
136
560
108
118
444
1...

output:

? 301 784
? 603 170
? 553 10
? 815 42
? 876 80
? 973 935
? 411 807
? 917 326
? 565 55
? 202 380
? 247 503
? 860 554
? 841 117
? 838 4
? 881 585
? 563 358
? 468 663
? 769 485
? 646 814
? 18 448
? 369 122
? 215 688
? 712 610
? 622 489
? 11 370
? 22 27
? 405 81
? 913 562
? 207 870
? 776 2
? 494 941
? 9...

result:

points 1.0 points  1.0 n = 1000, you used 1733 queries

Test #86:

score: 11
Accepted
time: 4ms
memory: 12596kb

input:

1000
552
319
84
187
200
293
147
143
149
476
198
124
9
233
41
91
410
266
87
176
222
183
648
214
226
403
47
108
512
132
251
308
368
636
197
13
680
107
863
114
22
503
125
241
692
223
404
610
272
708
6
345
489
453
32
282
481
351
538
150
517
67
21
770
285
246
270
242
312
681
48
121
494
110
63
260
56
907
...

output:

? 552 973
? 982 319
? 84 603
? 898 187
? 200 253
? 293 676
? 562 147
? 804 143
? 149 477
? 476 572
? 198 349
? 124 258
? 9 629
? 233 499
? 367 41
? 994 91
? 432 410
? 586 266
? 87 324
? 238 176
? 808 222
? 332 183
? 648 678
? 214 557
? 226 302
? 403 723
? 47 940
? 716 108
? 512 785
? 132 830
? 251 7...

result:

points 1.0 points  1.0 n = 1000, you used 1739 queries

Test #87:

score: 11
Accepted
time: 6ms
memory: 12616kb

input:

1000
368
383
128
376
423
523
488
157
133
680
524
364
601
11
134
534
68
588
495
259
41
668
802
4
324
162
685
179
476
171
114
190
46
269
90
120
848
167
963
80
20
129
845
122
467
690
515
446
511
87
670
79
71
522
414
854
663
525
654
385
676
103
65
173
55
538
425
444
370
512
461
233
13
32
323
341
115
125...

output:

? 368 581
? 923 383
? 128 151
? 376 754
? 423 892
? 981 523
? 770 488
? 642 157
? 351 133
? 680 852
? 524 615
? 574 364
? 601 933
? 11 337
? 960 134
? 534 602
? 555 68
? 588 653
? 518 495
? 259 750
? 360 41
? 668 757
? 928 802
? 4 148
? 324 728
? 162 344
? 824 685
? 527 179
? 648 476
? 171 198
? 114...

result:

points 1.0 points  1.0 n = 1000, you used 1621 queries

Subtask #3:

score: 34.0871
Acceptable Answer

Test #88:

score: 35.331
Acceptable Answer
time: 0ms
memory: 12644kb

input:

1500
726
839
441
182
393
332
43
783
411
221
867
296
31
101
300
993
580
477
90
583
284
1047
1170
713
557
153
731
309
459
486
349
352
360
11
214
318
427
244
987
280
1204
741
1192
1123
634
564
1131
407
121
154
608
939
582
4
44
1140
776
474
461
440
315
149
804
268
1042
205
760
816
681
425
612
34
712
668...

output:

? 976 726
? 839 1417
? 441 568
? 1161 182
? 393 1316
? 332 491
? 43 277
? 783 898
? 411 1338
? 1262 221
? 971 867
? 825 296
? 31 586
? 593 101
? 300 439
? 993 1121
? 889 580
? 558 477
? 836 90
? 1061 583
? 284 1007
? 1047 1144
? 1290 1170
? 1246 713
? 557 1276
? 529 153
? 1044 731
? 309 604
? 1472 4...

result:

points 0.44163700860 points  0.44163700860 n = 1500, you used 2498 queries

Test #89:

score: 40.8514
Acceptable Answer
time: 6ms
memory: 12692kb

input:

1500
471
978
151
269
863
580
53
1078
497
445
703
548
222
482
54
1087
704
351
423
721
281
488
108
200
684
182
19
720
733
434
472
757
390
663
359
1000
139
255
429
237
917
324
446
623
146
36
705
72
870
292
953
1
824
232
1387
617
690
486
495
983
503
819
887
823
661
257
911
729
717
556
213
736
179
440
43...

output:

? 1008 1030
? 523 62
? 1350 1249
? 152 1232
? 638 2
? 261 921
? 1448 175
? 423 123
? 96 1004
? 1056 754
? 798 354
? 953 355
? 1279 1189
? 1019 974
? 170 1447
? 414 34
? 764 797
? 457 1150
? 1078 40
? 327 780
? 1220 167
? 852 1013
? 1393 182
? 1301 1139
? 778 817
? 589 1319
? 1482 136
? 577 781
? 636...

result:

points 0.51064202710 points  0.51064202710 n = 1500, you used 2130 queries

Test #90:

score: 37.5284
Acceptable Answer
time: 14ms
memory: 12888kb

input:

1500
105
312
834
252
363
534
234
899
692
1239
62
415
279
722
7
972
348
139
196
46
140
454
889
943
203
524
1132
10
58
142
954
996
505
1314
104
576
495
1156
486
246
1012
890
776
443
407
716
36
1362
1006
82
752
250
670
78
514
1321
122
1178
263
212
693
227
1237
123
430
11
73
208
733
201
548
522
675
214
...

output:

? 1111 53
? 885 1345
? 915 1084
? 1375 515
? 182 1301
? 662 1234
? 1384 1107
? 450 671
? 679 1155
? 860 620
? 1470 1405
? 879 208
? 140 878
? 611 1140
? 931 4
? 730 1015
? 1219 1327
? 70 294
? 1403 118
? 1039 1478
? 731 1431
? 871 1274
? 445 986
? 472 869
? 102 1393
? 1239 423
? 935 928
? 1339 1496
...

result:

points 0.46910553080 points  0.46910553080 n = 1500, you used 2331 queries

Test #91:

score: 37.3422
Acceptable Answer
time: 10ms
memory: 12636kb

input:

1500
133
414
585
144
266
245
36
525
606
257
782
408
539
137
747
70
608
808
322
235
29
553
590
1081
793
638
185
514
1005
727
881
1323
11
571
262
1097
372
583
913
1080
89
717
943
125
331
498
27
127
724
246
65
875
885
43
205
1024
447
1143
1245
373
287
1172
602
649
841
884
626
501
693
876
107
679
919
64...

output:

? 1434 621
? 331 207
? 1208 496
? 1043 72
? 133 676
? 970 1378
? 18 1211
? 1238 1022
? 303 583
? 1372 347
? 391 840
? 204 940
? 1231 653
? 286 1432
? 891 1127
? 1006 35
? 304 423
? 1064 404
? 797 161
? 511 1383
? 1486 1295
? 1224 1002
? 525 295
? 960 756
? 1104 1014
? 319 376
? 432 1408
? 1075 257
?...

result:

points 0.46677712580 points  0.46677712580 n = 1500, you used 2344 queries

Test #92:

score: 40.5504
Acceptable Answer
time: 9ms
memory: 12616kb

input:

1500
992
627
1294
1242
506
80
107
499
369
71
82
380
603
359
1170
332
1405
1225
277
664
875
150
464
235
847
1212
212
236
181
1251
52
127
345
508
805
41
746
1359
122
145
518
916
222
140
135
478
373
94
314
1270
1014
715
484
230
690
1116
38
90
1338
548
354
102
545
817
274
628
814
182
310
58
264
691
111
...

output:

? 239 255
? 346 1064
? 1480 104
? 130 69
? 276 498
? 711 1375
? 804 1155
? 1000 1257
? 935 976
? 786 546
? 710 1144
? 561 1066
? 422 1052
? 930 108
? 166 163
? 585 29
? 1470 1453
? 1363 66
? 1420 889
? 1136 419
? 1188 1247
? 676 75
? 119 519
? 107 868
? 1255 1174
? 121 145
? 645 319
? 633 922
? 841 ...

result:

points 0.50688007440 points  0.50688007440 n = 1500, you used 2146 queries

Test #93:

score: 40.9854
Acceptable Answer
time: 9ms
memory: 12680kb

input:

1500
162
12
291
276
237
1024
302
167
823
463
573
827
548
112
386
76
1392
778
184
1081
155
1059
882
483
481
816
597
350
94
101
380
179
305
211
1057
1017
1320
663
1312
68
304
360
539
57
569
872
1123
588
795
724
1241
185
798
81
32
376
506
650
706
838
507
166
4
281
465
164
411
55
806
45
412
39
505
15
59...

output:

? 831 1414
? 756 993
? 605 1092
? 888 1363
? 632 983
? 9 1262
? 485 901
? 267 667
? 1193 339
? 519 1455
? 413 464
? 337 1339
? 1024 1292
? 806 12
? 229 943
? 1098 788
? 1446 38
? 1139 302
? 842 358
? 210 177
? 673 391
? 221 206
? 1191 308
? 509 183
? 1356 510
? 1158 156
? 139 452
? 551 925
? 797 462...

result:

points 0.51231802220 points  0.51231802220 n = 1500, you used 2123 queries

Test #94:

score: 34.4838
Acceptable Answer
time: 7ms
memory: 12644kb

input:

1500
281
305
441
996
9
894
375
5
247
36
872
165
187
287
810
940
82
309
194
600
661
1
118
520
590
252
12
897
236
566
88
307
799
669
436
392
15
310
67
69
828
646
141
148
500
225
922
319
8
1008
1322
521
1040
930
1009
178
845
776
1235
671
439
289
86
276
303
137
1069
858
478
806
555
74
682
770
356
227
38...

output:

? 1252 939
? 891 220
? 1208 619
? 492 1258
? 1483 237
? 1322 288
? 751 868
? 1192 1491
? 1007 1282
? 534 1429
? 246 244
? 1171 44
? 1276 1127
? 927 1414
? 120 1434
? 380 762
? 1337 1226
? 633 883
? 331 1113
? 301 212
? 340 179
? 625 1499
? 1095 1265
? 461 772
? 223 321
? 420 997
? 1254 1477
? 602 29...

result:

points 0.43104778940 points  0.43104778940 n = 1500, you used 2571 queries

Test #95:

score: 42.1581
Acceptable Answer
time: 8ms
memory: 12788kb

input:

1500
644
8
77
533
1011
63
280
304
402
262
327
722
232
219
422
481
197
435
309
401
1105
187
365
96
214
173
1060
672
132
425
739
150
930
149
845
310
832
1019
743
172
1253
10
159
817
357
602
819
680
450
445
785
123
837
392
654
364
382
1138
122
93
938
325
776
1281
813
349
443
582
75
924
279
65
391
991
6...

output:

? 1288 85
? 31 16
? 154 1305
? 1349 1066
? 979 903
? 126 1101
? 1060 560
? 752 608
? 804 1163
? 524 682
? 654 822
? 1444 499
? 464 759
? 438 233
? 854 844
? 962 993
? 394 1497
? 1185 870
? 618 838
? 685 802
? 791 183
? 374 573
? 730 803
? 192 938
? 428 766
? 346 400
? 881 83
? 145 1344
? 1381 264
? ...

result:

points 0.52697614030 points  0.52697614030 n = 1500, you used 2065 queries

Test #96:

score: 34.2838
Acceptable Answer
time: 11ms
memory: 12652kb

input:

1500
626
35
120
578
219
67
299
593
143
326
233
42
214
674
458
1121
651
772
764
695
790
755
114
1102
348
661
706
1312
149
689
498
298
288
654
276
394
113
53
571
1003
57
252
730
457
3
264
367
224
799
806
217
691
2
489
537
513
567
132
566
154
258
449
17
171
1095
463
225
809
590
874
193
180
64
909
377
1...

output:

? 974 627
? 242 34
? 121 1123
? 579 748
? 1413 218
? 946 66
? 298 910
? 782 592
? 825 142
? 327 328
? 232 543
? 43 99
? 480 215
? 855 675
? 720 459
? 1120 1140
? 1253 650
? 802 773
? 765 1007
? 694 736
? 1455 791
? 1014 754
? 115 1022
? 1196 1103
? 349 771
? 660 1471
? 707 1397
? 1419 1313
? 148 469...

result:

points 0.42854773160 points  0.42854773160 n = 1500, you used 2589 queries

Test #97:

score: 41.0434
Acceptable Answer
time: 0ms
memory: 12640kb

input:

1500
283
1203
590
288
553
179
279
412
956
526
351
957
33
180
134
390
385
73
1093
830
96
687
746
811
517
1110
1209
1060
850
1012
634
377
178
525
170
228
986
22
594
918
203
785
258
428
874
152
305
712
82
450
201
379
231
1204
86
1330
733
949
240
326
1048
613
995
36
215
49
597
144
89
120
745
823
222
12
...

output:

? 1219 185
? 299 44
? 692 910
? 976 1212
? 949 283
? 1323 471
? 1223 101
? 208 1088
? 271 544
? 974 552
? 1151 338
? 172 545
? 159 1469
? 1320 753
? 1366 513
? 1110 61
? 453 1117
? 1429 718
? 331 409
? 670 157
? 1404 707
? 238 815
? 570 754
? 336 691
? 904 985
? 360 390
? 247 293
? 440 59
? 650 365
...

result:

points 0.51304207830 points  0.51304207830 n = 1500, you used 2120 queries

Test #98:

score: 36.9368
Acceptable Answer
time: 4ms
memory: 12620kb

input:

1500
128
525
510
521
578
54
258
399
67
756
29
216
106
974
214
119
241
176
491
175
21
184
728
478
737
590
530
1065
186
183
373
612
410
809
310
822
180
506
588
631
407
78
796
397
490
143
576
851
151
725
652
114
937
378
199
681
517
498
1340
881
841
960
33
686
87
319
741
284
145
785
4
828
1072
577
777
9...

output:

? 821 641
? 914 318
? 29 301
? 589 1048
? 156 608
? 705 1337
? 639 1303
? 1040 1402
? 337 1257
? 1341 184
? 979 558
? 1431 250
? 1028 316
? 1459 349
? 296 488
? 1043 1195
? 1069 1026
? 1323 1197
? 1357 992
? 1296 1231
? 312 523
? 314 245
? 448 1254
? 673 666
? 19 216
? 1500 171
? 117 832
? 1167 58
?...

result:

points 0.46170966660 points  0.46170966660 n = 1500, you used 2373 queries

Test #99:

score: 38.7591
Acceptable Answer
time: 21ms
memory: 12696kb

input:

1500
139
10
363
1219
69
111
159
524
95
722
1134
691
155
288
496
218
700
162
205
406
779
663
86
230
543
23
1185
73
707
66
262
742
1087
271
622
692
228
961
530
1020
210
176
389
683
975
1315
93
80
576
997
181
593
384
193
785
899
589
15
1143
966
498
832
234
63
125
768
290
915
185
834
94
463
372
738
342
...

output:

? 539 1164
? 643 296
? 560 1406
? 270 1170
? 616 748
? 993 658
? 1168 219
? 1418 82
? 686 1281
? 1436 147
? 243 1027
? 821 1336
? 363 1020
? 502 73
? 571 341
? 225 1469
? 829 791
? 369 103
? 1069 1266
? 498 359
? 529 1009
? 268 157
? 631 954
? 59 78
? 1187 1033
? 298 1120
? 440 470
? 1160 153
? 489 ...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #100:

score: 38.2731
Acceptable Answer
time: 9ms
memory: 12900kb

input:

1500
923
977
271
262
107
597
104
334
632
741
196
555
495
324
285
130
115
613
278
19
449
749
931
220
1173
983
168
48
13
633
667
835
38
562
736
388
490
173
478
718
338
951
210
280
619
268
419
261
103
299
820
610
277
177
12
1341
337
241
100
966
25
43
1060
1172
10
911
139
1042
406
900
1137
581
374
418
1...

output:

? 766 809
? 909 250
? 140 1123
? 906 814
? 227 1318
? 434 777
? 1274 72
? 1179 1163
? 531 413
? 283 589
? 461 1077
? 1073 1147
? 238 535
? 1475 558
? 1327 1095
? 937 801
? 664 1244
? 716 1483
? 1091 731
? 1240 1279
? 518 1174
? 400 1456
? 923 7
? 60 1302
? 1315 775
? 1228 1237
? 597 947
? 472 225
? ...

result:

points 0.47841372750 points  0.47841372750 n = 1500, you used 2281 queries

Test #101:

score: 34.9057
Acceptable Answer
time: 2ms
memory: 12884kb

input:

1500
1028
1682
1802
1244
509
1592
417
2240
39
654
1429
2409
2527
1296
1348
781
710
1442
2198
166
1659
1022
2036
278
2263
68
416
2110
2332
53
1141
253
1422
430
680
1989
2081
2189
1947
898
1534
19
61
119
474
475
632
1188
1471
2572
588
955
670
299
2095
1379
647
324
956
1719
699
23
427
1207
1117
401
251...

output:

? 1393 513
? 966 849
? 1431 906
? 621 963
? 865 250
? 800 1413
? 202 833
? 1118 1349
? 1347 21
? 319 453
? 1128 714
? 1280 1203
? 1277 1263
? 647 718
? 675 1121
? 379 506
? 356 1205
? 722 999
? 1350 1095
? 110 84
? 1045 839
? 583 510
? 1239 1013
? 140 222
? 1418 1129
? 663 36
? 201 878
? 1050 1359
?...

result:

points 0.43632149170 points  0.43632149170 n = 1500, you used 2534 queries

Test #102:

score: 34.9989
Acceptable Answer
time: 3ms
memory: 12736kb

input:

1500
85347
85186
85485
85807
85368
85872
85124
85106
86180
85360
85179
85575
85046
85160
86042
85788
85710
85252
84995
85128
85238
85198
85677
85917
85071
85298
85514
85403
85032
85623
85091
85357
85174
85010
85316
85900
84968
85271
84943
85495
85457
85243
85365
85516
84912
85719
86008
85385
85894
8...

output:

? 615 447
? 524 287
? 585 803
? 907 1036
? 1408 468
? 972 1002
? 260 225
? 207 1170
? 1280 1304
? 460 564
? 280 1496
? 1093 675
? 288 147
? 261 1475
? 1474 1142
? 1314 888
? 1302 810
? 353 452
? 349 96
? 229 360
? 1305 339
? 299 1394
? 777 1346
? 1017 1306
? 172 764
? 603 398
? 614 1349
? 503 628
? ...

result:

points 0.43748654610 points  0.43748654610 n = 1500, you used 2526 queries

Test #103:

score: 34.2838
Acceptable Answer
time: 5ms
memory: 12644kb

input:

1500
5405
5653
5242
5422
6475
5726
8459
7680
5193
6917
7840
8717
7622
6254
7801
5978
5396
6421
9268
7063
7835
8703
9146
5932
7886
5350
6771
5463
5834
6680
6987
8856
7711
5548
7381
5484
8677
8345
6821
6043
8222
5206
5188
5163
7175
7823
6866
6410
5316
8760
6021
5379
8181
6238
7781
5921
6835
5948
6186
...

output:

? 322 131
? 1358 198
? 81 740
? 541 137
? 1146 460
? 1082 220
? 1080 1063
? 820 1483
? 58 651
? 594 624
? 877 1029
? 1478 1134
? 1361 796
? 387 604
? 858 1278
? 590 299
? 760 130
? 445 893
? 1465 1288
? 649 902
? 1218 875
? 1128 1275
? 1403 1256
? 281 636
? 961 889
? 118 429
? 550 851
? 147 310
? 25...

result:

points 0.42854773160 points  0.42854773160 n = 1500, you used 2589 queries

Test #104:

score: 34.8825
Acceptable Answer
time: 10ms
memory: 12872kb

input:

1500
4953
4130
5186
4024
4473
5171
4712
4433
4407
4097
4544
4840
4062
5022
4662
4997
4269
4190
4264
4203
4245
4391
4533
5279
4690
4066
5090
4610
4903
4615
4078
5176
4651
5093
4305
4095
4259
4652
4187
4586
4299
5057
5087
5184
5155
5075
5343
5125
4124
5032
4512
4694
5010
4289
4205
5366
5154
4901
4122
...

output:

? 763 713
? 220 100
? 1450 896
? 360 20
? 1499 361
? 884 952
? 542 1318
? 331 971
? 1015 315
? 752 75
? 492 412
? 1464 628
? 267 51
? 769 1344
? 502 1376
? 1293 747
? 212 846
? 149 602
? 1370 207
? 159 638
? 425 192
? 302 332
? 623 404
? 957 1086
? 523 1447
? 53 1466
? 819 1217
? 1197 461
? 672 1460...

result:

points 0.43603163660 points  0.43603163660 n = 1500, you used 2536 queries

Test #105:

score: 34.0871
Acceptable Answer
time: 18ms
memory: 12652kb

input:

1500
50208
66665
52708
61409
71359
63132
63545
60043
56358
51832
60198
70429
60952
74294
80149
67223
64972
50256
58890
58427
58079
69306
66778
55438
59953
53554
51123
76902
55342
51821
66858
58858
51376
77435
52580
52887
60514
63477
79949
56664
74792
67431
50237
83924
71099
70640
60925
50895
68212
5...

output:

? 1328 10
? 719 857
? 132 1490
? 586 495
? 1068 923
? 605 553
? 1488 577
? 1208 442
? 939 297
? 92 485
? 447 451
? 875 1365
? 1471 475
? 1032 1276
? 1262 1292
? 742 928
? 649 1465
? 1033 13
? 399 735
? 639 377
? 567 360
? 1055 827
? 722 1452
? 1210 250
? 438 1227
? 174 469
? 65 657
? 1271 1142
? 104...

result:

points 0.42608866010 points  0.42608866010 n = 1500, you used 2607 queries

Test #106:

score: 37.0889
Acceptable Answer
time: 7ms
memory: 12696kb

input:

1500
298
45
33
621
32
322
1101
135
30
687
563
1241
44
644
996
48
202
485
180
1023
583
335
1255
716
40
776
1068
475
34
400
1060
558
743
855
1193
463
864
365
127
887
280
260
46
670
186
1177
29
1208
329
1035
969
226
629
283
804
653
478
188
134
615
543
309
544
488
238
217
569
137
15
891
112
433
1030
108...

output:

? 698 1103
? 844 498
? 1033 910
? 1227 153
? 85 1412
? 796 393
? 1199 1404
? 693 747
? 1497 160
? 485 1190
? 1168 1076
? 675 374
? 449 774
? 618 859
? 1471 168
? 617 580
? 538 1032
? 380 35
? 271 767
? 543 294
? 1095 535
? 853 766
? 847 932
? 480 719
? 1339 1402
? 289 16
? 1229 820
? 607 1418
? 609 ...

result:

points 0.46361170940 points  0.46361170940 n = 1500, you used 2362 queries

Test #107:

score: 38.9852
Acceptable Answer
time: 3ms
memory: 12848kb

input:

1500
356
616
1092
861
55
498
228
859
489
782
767
680
842
1883
1062
780
647
103
1390
551
1514
828
1419
347
947
486
1379
300
67
1584
1557
421
4
1868
570
1396
869
379
582
326
581
879
1225
713
572
887
475
217
885
889
216
914
902
1170
1281
389
870
47
865
234
22
330
48
1126
79
369
656
1295
202
1475
431
17...

output:

? 712 1487
? 324 514
? 1151 775
? 863 757
? 956 996
? 1148 198
? 475 582
? 1071 1057
? 1164 406
? 138 332
? 659 1217
? 363 980
? 1025 422
? 226 771
? 350 850
? 1039 500
? 283 1483
? 1070 648
? 92 959
? 966 874
? 174 1096
? 492 1059
? 755 1189
? 1092 1058
? 1222 1493
? 1199 565
? 765 1049
? 941 517
?...

result:

points 0.48731548220 points  0.48731548220 n = 1500, you used 2236 queries

Test #108:

score: 38.4745
Acceptable Answer
time: 13ms
memory: 12928kb

input:

1500
85006
85290
86240
85283
85635
85780
85261
85017
85504
85767
85944
84925
85310
85207
85066
85665
85040
85622
85372
85477
86079
85219
85793
85300
85331
86096
86130
85417
85364
85786
86219
85353
85330
85260
85581
86060
85431
85379
85478
84924
85752
85082
85396
84990
85660
85779
85543
84995
85390
8...

output:

? 163 1167
? 919 1423
? 956 924
? 412 57
? 767 1068
? 944 1242
? 560 559
? 375 86
? 1012 642
? 1394 1304
? 1029 999
? 863 179
? 121 432
? 1037 1415
? 1324 1187
? 1135 1137
? 747 243
? 351 99
? 543 498
? 395 558
? 659 224
? 312 1467
? 339 1363
? 251 310
? 805 377
? 1115 408
? 796 903
? 1403 792
? 115...

result:

points 0.480931540 points  0.480931540 n = 1500, you used 2268 queries

Test #109:

score: 38.1356
Acceptable Answer
time: 3ms
memory: 12956kb

input:

1500
5989
5313
8282
9359
7391
5082
5987
5550
5311
6036
7446
6352
8087
7113
7396
8890
6197
9016
5502
6088
5510
8222
7160
5675
6416
7050
8271
7828
6046
6876
7982
6453
5586
5564
6075
9070
5658
7247
6866
5566
5919
6865
5720
5022
5334
6165
5179
9171
5129
8452
7486
5578
7861
5428
7481
8739
5359
6016
7460
...

output:

? 586 1408
? 419 52
? 351 1217
? 814 573
? 1107 862
? 7 111
? 266 1455
? 1312 357
? 1067 298
? 276 1114
? 998 36
? 1339 676
? 1321 131
? 739 1001
? 774 202
? 215 890
? 527 244
? 125 1203
? 1466 816
? 344 213
? 136 1
? 823 468
? 716 1398
? 476 1316
? 1245 1369
? 294 1098
? 16 562
? 604 917
? 290 1249...

result:

points 0.47669505820 points  0.47669505820 n = 1500, you used 2290 queries

Test #110:

score: 38.4902
Acceptable Answer
time: 0ms
memory: 12872kb

input:

1500
5339
5276
4149
4963
4196
4564
4911
4999
4315
4024
5326
5814
4068
5565
4947
4983
4175
4979
4030
5142
4537
4009
4672
4860
4444
5590
5043
4674
4428
5169
4525
5054
5011
4510
4266
5723
5810
4198
4653
5063
4079
4293
4130
5070
4766
4067
5462
4436
4684
4026
4223
4247
4129
4086
5419
5171
4147
4678
5302
...

output:

? 563 1051
? 1270 1065
? 226 160
? 99 663
? 193 116
? 435 261
? 1254 1153
? 73 1008
? 60 966
? 1072 457
? 284 651
? 802 589
? 1256 550
? 231 437
? 1013 1083
? 548 76
? 656 338
? 1151 431
? 1009 780
? 918 322
? 1428 49
? 1424 462
? 482 1026
? 692 433
? 1296 1484
? 1157 1320
? 959 372
? 394 1209
? 808...

result:

points 0.48112697980 points  0.48112697980 n = 1500, you used 2267 queries

Test #111:

score: 38.7112
Acceptable Answer
time: 7ms
memory: 12756kb

input:

1500
61840
79118
64304
57751
73093
52928
51642
79572
50636
59859
60994
73693
83100
76260
57962
56161
64767
55077
63042
57151
80978
64646
57395
65188
51632
56164
57688
55493
65820
51496
58800
57678
63862
65390
57728
56017
70426
61559
53824
66132
72269
67209
62754
66427
51477
60572
62355
83876
60119
7...

output:

? 161 1069
? 223 1010
? 1055 1062
? 1433 164
? 836 913
? 95 1347
? 11 599
? 248 1208
? 650 207
? 453 1344
? 736 1449
? 696 581
? 1408 883
? 115 144
? 994 966
? 78 1061
? 271 1074
? 1002 1462
? 384 992
? 639 1182
? 1255 586
? 311 580
? 611 308
? 1360 522
? 1137 1429
? 2 382
? 1001 621
? 235 27
? 1400...

result:

points 0.48389021580 points  0.48389021580 n = 1500, you used 2253 queries

Test #112:

score: 34.4391
Acceptable Answer
time: 23ms
memory: 12680kb

input:

1500
536
1322
526
44
628
144
10
15
1029
300
823
129
650
245
491
359
410
680
531
493
500
32
689
928
635
59
732
354
227
47
414
278
387
453
443
109
42
706
320
563
890
25
335
780
54
875
75
974
998
222
380
688
893
210
838
326
715
70
1038
612
1080
128
125
212
48
202
721
252
1430
406
55
317
218
712
872
113...

output:

? 878 536
? 1364 1322
? 526 1166
? 224 44
? 628 713
? 144 779
? 10 1016
? 15 64
? 1052 1029
? 300 1067
? 823 834
? 702 129
? 1221 650
? 245 774
? 748 491
? 359 1355
? 718 410
? 680 963
? 1131 531
? 493 929
? 500 659
? 388 32
? 1442 689
? 928 1207
? 635 1260
? 59 183
? 801 732
? 354 560
? 227 344
? 4...

result:

points 0.43048860890 points  0.43048860890 n = 1500, you used 2575 queries

Test #113:

score: 36.6381
Acceptable Answer
time: 0ms
memory: 12924kb

input:

1500
464
946
688
237
554
1254
1177
524
616
1279
287
503
110
710
320
99
88
340
463
154
75
21
488
76
961
349
101
182
141
194
32
447
192
1044
564
133
921
825
258
327
826
784
513
116
128
365
816
235
246
109
579
220
663
456
315
210
434
1187
568
561
367
20
762
645
366
95
55
272
171
167
358
11
644
587
768
...

output:

? 464 1029
? 946 968
? 688 1357
? 572 237
? 889 554
? 1263 1254
? 1177 1374
? 647 524
? 616 947
? 1279 1378
? 287 436
? 853 503
? 110 461
? 953 710
? 320 1241
? 786 99
? 660 88
? 1169 340
? 1141 463
? 990 154
? 160 75
? 330 21
? 516 488
? 380 76
? 961 1181
? 409 349
? 813 101
? 548 182
? 364 141
? 1...

result:

points 0.45797644230 points  0.45797644230 n = 1500, you used 2395 queries

Test #114:

score: 36.075
Acceptable Answer
time: 8ms
memory: 12900kb

input:

1500
507
76
515
412
221
213
767
687
305
889
909
320
729
86
735
325
223
658
203
451
962
875
437
285
166
201
351
1236
1110
244
231
754
379
856
667
554
971
189
165
321
61
472
119
137
502
1085
543
1207
504
541
542
562
227
736
199
456
92
153
1025
765
916
728
454
9
913
411
690
781
1227
156
1160
159
297
67...

output:

? 79 1305
? 787 829
? 773 232
? 34 887
? 501 294
? 598 745
? 325 1279
? 1148 352
? 1072 514
? 1370 1089
? 864 1323
? 520 87
? 604 286
? 609 658
? 1244 173
? 380 1394
? 714 545
? 1491 966
? 326 1458
? 709 708
? 19 1446
? 369 1084
? 1383 91
? 1476 1315
? 1055 456
? 1125 271
? 990 1313
? 208 1163
? 458...

result:

points 0.45093750760 points  0.45093750760 n = 1500, you used 2438 queries

Test #115:

score: 35.1994
Acceptable Answer
time: 10ms
memory: 12872kb

input:

1500
245
1341
513
987
443
144
268
578
1201
729
451
281
29
382
90
544
148
564
687
725
509
973
226
585
191
324
427
308
983
485
396
11
1097
1227
789
97
599
423
470
583
417
405
372
1029
1215
648
857
79
401
337
631
317
493
152
518
203
1228
497
970
535
938
419
1328
314
1319
24
756
333
457
527
1
343
227
54...

output:

? 245 863
? 1365 1341
? 862 513
? 987 1250
? 980 443
? 144 332
? 400 268
? 765 578
? 1308 1201
? 729 930
? 451 905
? 1360 281
? 29 1446
? 1391 382
? 90 997
? 544 890
? 490 148
? 1289 564
? 1080 687
? 1102 725
? 509 1057
? 1316 973
? 226 937
? 1240 585
? 191 201
? 324 1054
? 1232 427
? 1007 308
? 983...

result:

points 0.43999274690 points  0.43999274690 n = 1500, you used 2509 queries

Test #116:

score: 34.2838
Acceptable Answer
time: 11ms
memory: 12648kb

input:

1500
123
252
1015
105
588
890
381
405
1002
972
720
367
266
459
138
227
362
412
709
415
301
1186
20
233
772
829
41
869
529
770
221
140
743
286
958
883
220
109
413
302
1288
1491
775
482
77
65
179
324
61
834
621
901
586
1160
205
122
386
1240
425
643
1001
44
376
70
150
1323
162
366
635
822
740
143
613
2...

output:

? 311 123
? 860 252
? 1373 1015
? 105 1329
? 965 588
? 890 891
? 381 1210
? 405 490
? 1485 1002
? 1163 972
? 720 1136
? 367 392
? 266 813
? 1134 459
? 138 866
? 597 227
? 1478 362
? 913 412
? 1083 709
? 1063 415
? 301 1413
? 1231 1186
? 952 20
? 1379 233
? 772 905
? 829 861
? 41 1255
? 869 1356
? 52...

result:

points 0.42854773160 points  0.42854773160 n = 1500, you used 2589 queries

Test #117:

score: 34.2618
Acceptable Answer
time: 11ms
memory: 12780kb

input:

1500
510
376
334
364
630
445
212
338
267
35
66
1079
150
1029
973
440
666
780
562
1037
1399
458
232
1219
277
3
172
995
95
816
447
971
208
155
466
115
783
321
154
835
542
685
196
1356
78
629
109
603
59
1126
670
954
1048
1089
124
736
48
255
735
87
469
1076
422
239
213
889
527
390
263
165
434
240
524
65...

output:

? 510 1087
? 376 871
? 334 1119
? 609 364
? 630 880
? 968 445
? 212 1164
? 338 1402
? 1484 267
? 35 910
? 293 66
? 1079 1216
? 1465 150
? 1045 1029
? 1221 973
? 1241 440
? 666 1417
? 780 1047
? 562 1090
? 1365 1037
? 1459 1399
? 458 1225
? 536 232
? 1453 1219
? 277 341
? 1069 3
? 172 288
? 995 1490
...

result:

points 0.42827250210 points  0.42827250210 n = 1500, you used 2591 queries