QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#765793#8267. Staring Contest_8_8_#52.382174 15ms12860kbC++204.1kb2024-11-20 15:18:082024-11-20 15:18:08

Judging History

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

  • [2024-11-20 15:18:08]
  • 评测
  • 测评结果:52.382174
  • 用时:15ms
  • 内存:12860kb
  • [2024-11-20 15:18:08]
  • 提交

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;
    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);
        }
    }
    // cout << (int)x.size() << ' ' << (int)nx.size() << '\n';
    assert((int)nx.size() <= ((int)x.size() + 1) / 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: 1ms
memory: 12632kb

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #2:

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

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: 3ms
memory: 12576kb

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: 12808kb

input:

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

output:

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

result:

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

Test #5:

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

input:

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

output:

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

result:

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

Test #6:

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

input:

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

output:

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

result:

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

Test #7:

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

input:

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

output:

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

result:

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

Test #8:

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

input:

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

output:

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

result:

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

Test #9:

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

input:

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

output:

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

result:

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

Test #10:

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

input:

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

output:

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

result:

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

Test #11:

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

input:

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

output:

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

result:

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

Test #12:

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

input:

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

output:

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

result:

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

Test #13:

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

input:

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

output:

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

result:

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

Test #14:

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

input:

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

output:

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

result:

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

Test #15:

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

input:

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

output:

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

result:

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

Test #16:

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

input:

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

output:

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

result:

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

Test #17:

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

input:

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

output:

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

result:

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

Test #18:

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

input:

50
86362
86361
86364
86394
86371
86350
86352
86359
86355
86363
86370
86351
86357
86385
86354
86372
86353
86386
86356
86374
86380
86377
86368
86358
86365
86391
86385
86380
86394
86396
86371
86370
86373
86364
86365
86366
86359
86358
86379
86356
86367
86352
86360
86350
86360
86367
86376
86379
86382
863...

output:

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

result:

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

Test #19:

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

input:

50
8198
6824
6767
6651
6926
5703
7174
7026
5076
5773
5302
7663
9512
7563
7993
8947
5406
5914
7560
6476
5454
6109
7779
6297
7233
9512
9838
8060
9491
8006
7026
7060
8098
6651
8939
6109
5914
8464
7159
5813
8878
5813
6375
7159
8060
8143
8464
8917
9032
9404
9654
9838
9732
9491
9258
8917
8883
8464
8143
80...

output:

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

result:

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

Test #20:

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

input:

50
5033
5054
5038
5084
5023
5030
5076
5049
5046
5003
5036
5004
5035
5027
5062
5025
5024
5048
5017
5031
5083
5000
5010
5021
5005
5084
5076
5062
5054
5049
5088
5038
5036
5035
5033
5031
5046
5027
5072
5029
5021
5010
5052
5003
5004
5000
5039
5050
5052
5059
5065
5068
5072
5075
5081
5085
5096
5088
5086
50...

output:

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

result:

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

Test #21:

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

input:

50
54556
68114
59551
72805
75191
58109
50918
60767
53250
54962
50293
62431
67305
67289
70891
52604
56501
51290
52428
57154
68459
57364
56134
69824
52391
75191
70891
80336
68114
68459
67638
60767
62431
58109
78936
56501
56134
54962
54556
58019
52428
52604
65062
50293
50918
58019
65062
66780
70252
738...

output:

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

result:

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

Test #22:

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

input:

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

output:

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

result:

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

Test #23:

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

input:

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

output:

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

result:

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

Test #24:

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

input:

50
86365
86388
86362
86384
86354
86361
86373
86359
86370
86350
86378
86351
86356
86369
86352
86382
86363
86364
86353
86377
86358
86357
86385
86371
86355
86385
86388
86382
86389
86392
86371
86369
86365
86376
86363
86361
86372
86357
86358
86367
86353
86352
86375
86360
86394
86379
86381
86376
86397
863...

output:

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

result:

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

Test #25:

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

input:

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

output:

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

result:

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

Test #26:

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

input:

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

output:

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

result:

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

Test #27:

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

input:

50
75075
73081
51658
70576
83944
62248
54630
53987
54250
57318
70928
58746
67005
61401
75023
68422
62990
58357
61968
53213
53454
67146
72291
72585
67069
79358
79047
78154
72585
82479
70928
70576
68422
83944
67069
67005
62990
65477
61968
72620
58357
58746
55504
58717
66448
80461
79047
77213
73863
726...

output:

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

result:

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

Test #28:

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

input:

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

output:

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

result:

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

Test #29:

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

input:

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

output:

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

result:

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

Test #30:

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

input:

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

output:

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

result:

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

Test #31:

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

input:

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

output:

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

result:

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

Test #32:

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

input:

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

output:

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

result:

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

Test #33:

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

input:

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

output:

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

result:

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

Test #34:

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

input:

4
3
2
2
5

output:

? 3 2
? 1 4
? 1 2
? 3 4
! 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: 12580kb

input:

4
3
2
3
5

output:

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

result:

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

Test #36:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #37:

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

input:

4
3
2
3
2
5

output:

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

result:

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

Test #38:

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

input:

4
2
3
2
3
5

output:

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

result:

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

Test #39:

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

input:

4
3
2
3
5

output:

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

result:

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

Test #40:

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

input:

4
3
2
5

output:

? 4 1
? 2 3
? 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: 0ms
memory: 12808kb

input:

4
2
3
2
3
5

output:

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

result:

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

Test #42:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #43:

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

input:

4
5
2
2
3

output:

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

result:

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

Test #44:

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

input:

4
2
3
2
3
5

output:

? 2 3
? 1 4
? 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: 12612kb

input:

4
5
2
2
3

output:

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

result:

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

Test #46:

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

input:

4
5
2
2
3
3

output:

? 4 1
? 2 3
? 2 1
? 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: 0ms
memory: 12604kb

input:

4
3
2
2
5
3

output:

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

result:

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

Test #48:

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

input:

4
3
2
5

output:

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

result:

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

Test #49:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #50:

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

input:

4
2
5
3
3

output:

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

result:

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

Test #51:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #52:

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

input:

4
2
5
3
3

output:

? 2 3
? 1 4
? 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: 12632kb

input:

4
2
5
3

output:

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

result:

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

Test #54:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #55:

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

input:

4
2
3
2
3
5

output:

? 4 1
? 2 3
? 4 2
? 1 2
? 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: 12512kb

input:

4
2
5
2
3

output:

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

result:

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

Test #57:

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

input:

4
5
2
3
3

output:

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

result:

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

Subtask #2:

score: 11
Accepted

Test #58:

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

input:

1000
271
135
394
529
229
367
9
115
296
200
440
672
217
716
374
258
251
302
609
36
541
40
177
467
215
80
248
312
683
426
542
118
47
324
219
491
138
222
559
822
729
344
76
579
885
23
797
414
275
909
96
500
113
419
346
73
746
134
317
69
91
92
715
280
872
540
473
267
404
126
699
43
20
46
15
71
835
243
1...

output:

? 271 510
? 638 135
? 394 788
? 529 563
? 229 807
? 367 647
? 584 9
? 115 499
? 402 296
? 949 200
? 440 887
? 672 959
? 535 217
? 911 716
? 374 622
? 258 906
? 251 671
? 606 302
? 609 727
? 94 36
? 927 541
? 40 49
? 177 196
? 890 467
? 918 215
? 714 80
? 248 802
? 312 676
? 973 683
? 689 426
? 971 5...

result:

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

Test #59:

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

input:

1000
186
153
567
470
29
453
204
38
22
704
532
718
142
215
425
540
209
223
5
184
132
358
737
300
387
758
573
36
148
52
141
2
20
376
118
218
329
610
525
57
116
345
19
520
243
158
326
113
80
605
261
247
620
438
253
761
53
615
282
350
392
66
203
293
182
159
510
516
121
100
481
37
767
455
513
14
46
608
3...

output:

? 815 40
? 584 848
? 132 434
? 531 479
? 972 632
? 169 548
? 29 797
? 963 374
? 313 979
? 46 297
? 469 82
? 228 283
? 281 859
? 464 786
? 456 576
? 270 461
? 69 792
? 778 633
? 986 996
? 817 80
? 384 869
? 95 643
? 264 72
? 701 176
? 614 599
? 243 88
? 309 428
? 965 38
? 480 853
? 949 143
? 835 860
...

result:

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

Test #60:

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

input:

1000
163
314
18
469
275
438
481
482
182
299
177
127
541
144
551
487
16
669
451
242
235
434
34
729
366
734
72
2
196
721
622
899
342
107
262
683
25
105
28
726
102
192
50
561
455
345
86
106
37
819
71
112
289
169
168
146
579
421
190
859
255
407
248
409
98
394
528
210
391
252
595
80
201
294
176
203
458
1...

output:

? 82 92
? 816 844
? 992 313
? 235 675
? 461 138
? 782 308
? 241 707
? 682 760
? 655 910
? 150 333
? 89 494
? 64 407
? 353 271
? 929 478
? 276 453
? 317 244
? 765 993
? 456 335
? 226 427
? 775 880
? 118 728
? 784 644
? 383 984
? 365 574
? 818 781
? 634 434
? 124 965
? 1000 642
? 744 903
? 399 361
? 6...

result:

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

Test #61:

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

input:

1000
180
32
164
565
465
247
295
731
434
850
93
155
528
872
172
618
158
57
600
175
149
730
198
82
846
435
533
156
767
326
425
8
725
98
787
387
40
306
189
331
1
321
491
273
557
487
249
137
272
547
52
250
5
142
258
22
284
144
70
421
11
348
654
779
525
457
124
109
651
539
744
99
302
25
67
81
127
187
113...

output:

? 90 642
? 375 16
? 82 603
? 718 335
? 768 244
? 636 877
? 399 853
? 635 404
? 217 284
? 425 516
? 954 179
? 923 519
? 367 264
? 444 436
? 86 376
? 380 309
? 452 79
? 733 972
? 300 495
? 913 759
? 926 595
? 500 365
? 751 99
? 74 41
? 423 490
? 783 448
? 432 734
? 752 78
? 501 617
? 163 587
? 788 437...

result:

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

Test #62:

score: 11
Accepted
time: 15ms
memory: 12608kb

input:

1000
362
864
95
184
80
137
189
3
75
481
306
168
162
76
545
210
919
131
133
304
77
648
485
104
72
147
512
26
410
187
283
23
504
67
307
57
148
245
191
37
710
802
361
179
633
636
44
177
342
581
435
297
763
705
47
181
272
670
737
207
543
565
31
403
138
270
182
273
551
163
144
456
848
620
48
310
102
152
...

output:

? 320 60
? 53 69
? 548 214
? 409 403
? 644 461
? 98 569
? 595 132
? 502 628
? 538 989
? 236 741
? 184 348
? 417 172
? 420 641
? 682 463
? 773 907
? 313 396
? 14 960
? 85 566
? 643 567
? 140 349
? 91 539
? 177 883
? 802 743
? 449 667
? 465 755
? 574 147
? 245 55
? 966 488
? 726 296
? 594 837
? 642 20...

result:

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

Test #63:

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

input:

1000
730
882
420
650
354
330
232
180
122
457
480
85
203
869
404
72
628
206
624
95
323
61
74
499
25
118
722
320
338
820
221
590
181
243
286
690
625
757
265
46
69
10
154
535
49
553
865
132
379
89
124
164
105
432
47
162
42
97
44
347
363
750
418
23
93
149
260
67
15
294
862
94
667
372
75
348
111
114
601
...

output:

? 865 938
? 14 941
? 710 868
? 825 959
? 677 884
? 665 766
? 616 344
? 590 680
? 561 295
? 862 272
? 740 236
? 458 625
? 399 213
? 30 66
? 215 702
? 4 536
? 814 824
? 603 76
? 153 812
? 42 453
? 339 978
? 470 214
? 284 537
? 143 251
? 74 488
? 724 559
? 997 861
? 26 660
? 669 738
? 910 34
? 390 722
...

result:

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

Test #64:

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

input:

1000
588
625
133
32
112
655
332
305
323
351
575
205
29
594
76
96
7
200
199
313
222
689
407
275
89
301
369
337
686
621
524
243
499
750
221
142
276
562
368
315
410
640
435
532
178
150
218
56
411
454
49
509
144
432
159
281
406
217
668
33
192
872
349
20
148
125
154
292
546
751
63
619
792
409
95
285
685
...

output:

? 176 318
? 250 610
? 359 735
? 447 937
? 777 530
? 310 716
? 337 38
? 578 391
? 300 355
? 299 474
? 248 150
? 544 591
? 943 538
? 188 354
? 849 896
? 809 536
? 987 113
? 601 283
? 252 603
? 375 374
? 557 507
? 378 692
? 187 768
? 451 632
? 823 697
? 399 432
? 211 263
? 327 281
? 850 372
? 904 242
?...

result:

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

Test #65:

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

input:

1000
356
3
837
390
129
194
835
262
41
426
388
174
544
568
650
604
403
140
244
581
133
412
338
506
776
249
233
24
391
115
182
151
742
497
138
176
402
223
348
269
189
317
444
449
320
413
31
40
637
475
648
279
184
476
540
435
89
737
222
39
83
293
696
237
369
275
111
416
38
697
197
230
382
327
437
563
4...

output:

? 712 483
? 760 6
? 155 327
? 780 843
? 615 258
? 388 892
? 331 53
? 427 524
? 82 903
? 852 383
? 776 941
? 348 3
? 459 913
? 865 343
? 701 385
? 543 793
? 836 806
? 280 337
? 488 395
? 487 839
? 587 266
? 403 824
? 676 988
? 989 883
? 449 311
? 333 498
? 977 466
? 413 48
? 782 834
? 230 682
? 568 3...

result:

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

Test #66:

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

input:

1000
441
35
310
150
499
816
333
673
819
28
8
260
325
71
406
302
33
448
525
343
814
435
704
589
635
257
9
558
245
27
247
322
125
570
515
419
49
862
546
425
464
461
714
948
192
509
789
597
577
723
337
735
497
67
614
56
72
781
95
492
200
155
152
426
176
167
632
282
86
37
794
268
450
74
96
547
717
90
66...

output:

? 998 440
? 34 799
? 688 311
? 151 248
? 498 870
? 972 817
? 332 982
? 672 892
? 818 937
? 29 707
? 662 9
? 492 261
? 803 324
? 70 126
? 407 624
? 368 303
? 32 873
? 449 796
? 563 524
? 342 441
? 947 815
? 438 434
? 822 705
? 781 588
? 634 931
? 256 810
? 494 8
? 610 559
? 876 244
? 26 217
? 896 246...

result:

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

Test #67:

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

input:

1000
234
830
741
139
331
166
385
55
28
183
160
265
4
124
723
51
367
30
33
431
85
689
658
189
157
786
108
356
154
505
83
811
279
714
376
484
895
170
706
191
362
504
8
535
46
66
498
123
254
241
161
271
88
36
483
931
53
233
425
400
848
48
555
681
258
842
146
370
19
293
479
75
576
106
491
312
475
860
75...

output:

? 179 766
? 72 170
? 174 261
? 863 231
? 116 671
? 266 834
? 617 74
? 947 5
? 972 366
? 394 819
? 840 546
? 737 204
? 14 996
? 428 876
? 279 125
? 197 951
? 635 143
? 970 446
? 607 969
? 571 165
? 227 917
? 137 313
? 309 342
? 536 813
? 845 290
? 89 214
? 892 680
? 220 644
? 846 160
? 497 269
? 838 ...

result:

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

Test #68:

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

input:

300
8
49
55
249
6
131
154
178
12
198
42
135
195
130
46
158
7
44
203
141
105
182
82
97
4
90
172
113
202
61
265
14
22
76
197
77
281
102
145
35
94
120
146
278
32
91
103
52
118
15
31
126
161
16
45
189
37
117
171
78
23
140
11
72
3
151
1
159
196
13
248
56
53
190
112
2
25
213
29
18
62
67
124
221
184
143
18...

output:

? 10 8
? 49 243
? 187 55
? 299 249
? 136 6
? 258 131
? 154 228
? 178 262
? 96 12
? 216 198
? 122 42
? 135 242
? 195 200
? 130 287
? 50 46
? 290 158
? 7 280
? 100 44
? 215 203
? 141 205
? 105 175
? 182 247
? 244 82
? 97 116
? 86 4
? 125 90
? 172 245
? 113 165
? 202 237
? 217 61
? 265 300
? 14 63
? 26...

result:

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

Test #69:

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

input:

300
3
210
260
44
173
281
212
170
17
67
286
6
152
171
101
121
37
94
11
25
45
130
98
116
218
41
104
119
68
199
71
24
180
231
82
150
14
156
15
39
92
274
43
66
33
107
87
46
125
64
9
188
70
200
63
59
147
36
76
19
21
221
223
12
206
30
28
120
2
7
60
22
159
158
40
140
115
10
133
4
72
32
42
31
49
5
117
181
1...

output:

? 243 249
? 166 273
? 100 13
? 167 252
? 53 287
? 279 117
? 17 45
? 92 270
? 112 289
? 122 175
? 24 61
? 84 99
? 72 77
? 19 181
? 170 56
? 248 236
? 195 12
? 125 68
? 274 21
? 163 237
? 138 145
? 206 151
? 39 161
? 225 210
? 192 183
? 134 299
? 135 232
? 155 220
? 108 278
? 227 266
? 281 96
? 44 176...

result:

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

Test #70:

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

input:

1000
748
379
63
76
358
760
91
441
472
11
208
666
715
486
85
70
649
334
237
29
222
726
614
216
357
161
207
3
279
783
121
53
183
203
945
838
5
28
195
599
500
119
378
51
39
55
13
278
433
501
413
159
439
427
196
145
493
613
227
189
54
154
478
734
297
226
257
27
74
489
105
804
632
239
575
52
92
352
20
14...

output:

? 210 835
? 384 590
? 31 174
? 870 674
? 466 899
? 331 23
? 494 232
? 24 818
? 976 341
? 398 586
? 978 929
? 575 395
? 208 241
? 677 931
? 626 577
? 349 150
? 990 505
? 932 764
? 475 969
? 454 847
? 959 220
? 366 171
? 612 574
? 926 385
? 834 432
? 648 624
? 502 717
? 11 592
? 518 93
? 974 613
? 544...

result:

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

Test #71:

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

input:

1000
1373
1431
1758
11
1749
787
236
365
246
455
360
706
780
534
109
314
1635
119
673
1812
380
44
160
834
1215
803
4
1692
1400
476
90
27
416
654
758
340
1021
181
733
1258
719
33
799
276
135
1106
226
58
318
1654
442
417
1183
794
1855
1015
817
171
1257
912
334
904
634
1102
854
1031
1156
592
252
1398
14...

output:

? 876 697
? 776 731
? 926 874
? 808 7
? 871 982
? 878 405
? 335 124
? 978 191
? 130 961
? 342 238
? 987 187
? 366 803
? 471 401
? 282 317
? 543 63
? 959 162
? 826 883
? 69 616
? 735 350
? 932 898
? 364 199
? 31 90
? 84 940
? 430 507
? 620 683
? 415 579
? 2 99
? 846 856
? 713 740
? 972 248
? 52 357
?...

result:

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

Test #72:

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

input:

1000
85564
85830
85685
85491
85591
85476
85803
85788
85614
85496
85734
85532
86026
85630
85836
85650
85558
86200
86128
85784
85418
85449
85470
85918
85562
85648
85520
85475
85863
86144
85505
85764
85533
85460
86017
85680
86093
85635
85611
85456
85844
85815
85453
85548
85811
85447
85719
86372
85535
8...

output:

? 611 165
? 523 431
? 766 286
? 92 705
? 192 514
? 77 860
? 404 415
? 699 389
? 215 977
? 995 97
? 534 335
? 133 987
? 626 930
? 231 903
? 437 681
? 251 731
? 159 334
? 807 800
? 762 728
? 385 526
? 529 19
? 50 689
? 767 71
? 952 518
? 900 163
? 249 806
? 121 793
? 76 628
? 464 590
? 744 998
? 106 4...

result:

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

Test #73:

score: 11
Accepted
time: 8ms
memory: 12608kb

input:

1000
8016
6784
5728
9266
7096
5851
5767
7951
7475
8655
6791
6375
7394
8264
5998
8247
6369
5867
5516
6384
8397
6745
6428
5736
6967
6100
8670
7165
6481
9110
8556
8114
5104
8851
7751
6753
6048
8293
7532
5588
6019
5244
5865
5957
7993
5480
5446
9454
8403
5092
5022
6089
6427
7891
6935
5423
8405
7493
5425
...

output:

? 767 578
? 694 318
? 126 971
? 855 905
? 724 392
? 142 820
? 131 813
? 881 565
? 459 950
? 717 814
? 319 716
? 680 240
? 442 877
? 628 818
? 985 173
? 623 673
? 386 239
? 145 965
? 84 885
? 243 310
? 898 659
? 577 309
? 644 252
? 127 668
? 916 358
? 198 253
? 990 721
? 403 660
? 746 264
? 817 947
?...

result:

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

Test #74:

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

input:

1000
5277
5454
4820
5292
5754
4975
5122
4612
4527
4136
4712
5050
4220
5096
4511
5239
4406
4203
4100
4085
4264
4011
4938
4030
5314
4566
4613
4010
4525
4246
4194
4350
4079
4419
4838
4456
5992
4368
4082
4200
5703
4897
4005
5093
4105
4131
5691
4161
4896
4285
5354
4843
4259
4223
4061
4615
4181
4178
4890
...

output:

? 641 942
? 810 727
? 586 406
? 649 776
? 878 965
? 584 486
? 559 845
? 305 819
? 711 266
? 909 72
? 877 356
? 522 766
? 119 493
? 545 897
? 258 911
? 976 621
? 212 696
? 286 112
? 165 51
? 40 749
? 143 396
? 215 7
? 517 467
? 15 593
? 843 660
? 881 279
? 306 590
? 353 6
? 382 265
? 133 825
? 108 14...

result:

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

Test #75:

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

input:

1000
59750
63965
52149
59255
75573
66108
76242
62696
75820
75812
64361
53224
70241
51431
70260
81942
65402
50837
55918
65998
52637
69372
58772
67498
75565
56469
65192
59763
56711
58084
53271
56131
61075
59894
56041
61207
74007
54715
77870
50756
73146
70890
66382
55737
62568
54159
75076
57818
53979
6...

output:

? 255 484
? 850 366
? 51 602
? 842 246
? 721 967
? 718 433
? 738 984
? 865 337
? 726 819
? 848 725
? 379 883
? 83 523
? 555 655
? 34 728
? 927 556
? 926 889
? 410 663
? 21 477
? 307 143
? 446 430
? 68 548
? 610 518
? 235 770
? 479 780
? 719 930
? 225 161
? 404 424
? 256 782
? 172 801
? 553 221
? 85 ...

result:

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

Test #76:

score: 11
Accepted
time: 14ms
memory: 12608kb

input:

1000
194
148
180
429
469
788
75
44
266
425
446
247
260
308
564
320
762
51
216
487
164
57
284
340
842
233
113
60
725
333
310
207
627
520
9
342
5
654
361
268
427
298
25
886
676
584
684
127
189
404
205
635
692
275
436
7
135
468
172
24
778
295
656
171
187
944
557
101
413
303
456
753
179
174
231
202
769
...

output:

? 851 964
? 863 712
? 277 961
? 873 79
? 933 265
? 111 903
? 362 881
? 346 454
? 166 494
? 193 584
? 478 95
? 613 290
? 50 35
? 305 130
? 990 628
? 47 29
? 329 158
? 862 407
? 98 595
? 24 611
? 3 677
? 864 891
? 620 43
? 65 1
? 354 402
? 734 530
? 363 519
? 196 829
? 502 717
? 200 752
? 436 468
? 31...

result:

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

Test #77:

score: 11
Accepted
time: 8ms
memory: 12672kb

input:

1000
352
553
643
10
425
1012
1167
516
1226
128
89
267
902
1435
706
1240
1409
33
477
731
525
505
1579
258
148
565
644
779
1381
429
1029
1197
581
1267
233
494
1503
351
771
1761
864
246
1083
308
1476
765
770
584
1043
698
249
47
650
1186
424
623
580
549
574
1351
111
856
1038
339
888
200
1853
218
86
444
...

output:

? 996 536
? 630 827
? 217 655
? 706 914
? 523 992
? 462 919
? 736 789
? 83 544
? 427 92
? 574 179
? 749 602
? 562 776
? 403 702
? 850 733
? 998 404
? 305 626
? 498 824
? 48 986
? 569 232
? 854 715
? 505 549
? 167 495
? 945 902
? 953 228
? 970 263
? 275 834
? 799 947
? 306 414
? 472 153
? 884 173
? 3...

result:

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

Test #78:

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

input:

1000
85598
86250
85968
85474
85467
85581
85538
85501
86302
85612
85551
85741
85626
85622
85687
85487
85564
86001
85701
85431
85481
85674
85665
85905
86097
85958
85645
86139
85776
85798
85743
85828
85950
85446
85422
85756
85821
85705
85915
85517
85989
85864
85425
85909
86132
85951
85415
86245
85595
8...

output:

? 348 862
? 153 192
? 342 930
? 385 801
? 437 188
? 249 341
? 177 525
? 435 615
? 194 663
? 36 791
? 55 7
? 87 552
? 848 145
? 917 327
? 903 904
? 887 54
? 427 722
? 911 83
? 81 498
? 555 2
? 16 543
? 389 851
? 891 783
? 375 860
? 974 823
? 399 601
? 224 723
? 924 638
? 654 926
? 307 384
? 694 322
?...

result:

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

Test #79:

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

input:

1000
7180
5047
5761
7810
9434
6815
5115
7250
6216
5989
7249
6299
8330
8713
5916
5634
6963
5827
5106
6473
8498
6719
8569
5272
5065
7477
8375
6072
7497
5799
5210
5461
7562
6622
6457
5066
9140
5056
7382
7452
5184
6625
6526
5668
5725
7650
6297
5223
6325
5053
5162
8642
6128
5164
8632
6062
5962
8255
5947
...

output:

? 889 413
? 937 63
? 492 233
? 783 993
? 883 25
? 670 643
? 633 318
? 765 348
? 281 565
? 422 298
? 549 237
? 620 752
? 205 955
? 891 772
? 603 874
? 192 45
? 659 37
? 339 75
? 960 338
? 328 451
? 398 978
? 176 352
? 98 982
? 539 654
? 239 358
? 780 260
? 197 904
? 264 550
? 638 836
? 73 707
? 745 5...

result:

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

Test #80:

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

input:

1000
4789
4267
5149
4755
4260
4793
5163
4399
4389
5140
5060
4677
4468
4113
4990
5597
4043
5191
5134
4335
5619
4767
4641
5035
4334
5453
5599
5477
5606
4702
4104
4204
4078
4834
4216
4305
4769
4067
5259
4370
4763
5586
4963
5435
4054
4423
4549
5501
5011
4026
4083
5152
4507
4351
4418
4410
5473
4551
5478
...

output:

? 724 607
? 438 74
? 641 274
? 569 176
? 624 501
? 463 112
? 679 402
? 171 984
? 62 232
? 756 696
? 731 39
? 573 306
? 242 432
? 137 388
? 926 220
? 78 944
? 844 570
? 466 322
? 812 380
? 909 963
? 479 154
? 946 211
? 505 357
? 418 962
? 621 576
? 903 487
? 828 680
? 637 314
? 181 716
? 612 24
? 379...

result:

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

Test #81:

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

input:

1000
57127
71528
69194
66720
64689
62150
66528
51660
78622
62727
54293
70161
53235
76051
51848
52047
63379
63472
51355
66804
56200
59120
53727
78149
63988
68768
69956
77849
51012
51980
50471
73879
61061
75249
53553
51503
77126
67616
66553
56376
58136
54240
55860
62366
60715
59103
54218
73099
60585
7...

output:

? 506 198
? 522 636
? 806 820
? 365 755
? 373 205
? 346 422
? 304 861
? 455 883
? 571 808
? 102 371
? 239 233
? 298 169
? 446 535
? 646 182
? 161 294
? 338 499
? 165 979
? 377 905
? 341 561
? 482 749
? 994 166
? 931 779
? 599 397
? 466 152
? 791 758
? 565 171
? 185 438
? 202 276
? 895 687
? 57 27
? ...

result:

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

Test #82:

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

input:

1000
88
208
12
344
202
189
294
463
66
158
438
49
264
231
61
634
250
646
358
150
258
373
810
17
311
615
27
118
140
372
377
101
252
713
738
362
177
58
507
570
338
350
487
2
92
267
795
606
117
399
29
280
268
46
792
107
109
757
655
32
39
142
106
192
168
659
453
676
777
128
549
18
559
266
285
406
323
67
...

output:

? 88 944
? 932 208
? 392 12
? 497 344
? 202 482
? 356 189
? 294 395
? 754 463
? 950 66
? 158 249
? 468 438
? 49 541
? 264 700
? 231 781
? 171 61
? 814 634
? 250 525
? 844 646
? 579 358
? 543 150
? 493 258
? 490 373
? 978 810
? 17 534
? 311 664
? 615 638
? 27 300
? 154 118
? 856 140
? 372 772
? 582 3...

result:

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

Test #83:

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

input:

1000
24
350
7
123
346
532
204
10
393
688
693
435
452
836
255
73
367
192
66
280
699
95
29
539
27
289
90
149
380
675
17
201
208
730
220
130
158
128
198
524
396
188
148
211
310
110
854
273
520
338
258
162
574
187
89
359
313
559
445
9
552
653
71
670
633
288
296
185
293
325
115
348
120
224
341
122
785
28...

output:

? 24 137
? 764 350
? 7 756
? 123 413
? 346 638
? 532 683
? 523 204
? 10 374
? 393 801
? 688 721
? 722 693
? 435 439
? 452 972
? 836 979
? 255 606
? 73 118
? 615 367
? 546 192
? 66 620
? 280 916
? 699 738
? 880 95
? 953 29
? 631 539
? 27 392
? 289 870
? 90 387
? 149 611
? 576 380
? 724 675
? 47 17
? ...

result:

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

Test #84:

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

input:

1000
68
175
523
298
338
114
263
41
429
347
359
216
267
67
537
302
634
452
317
428
691
26
346
184
45
591
3
400
131
141
179
7
645
631
358
18
829
544
848
385
522
738
37
541
449
205
212
514
102
252
54
555
681
75
260
33
116
23
671
766
386
547
20
369
89
295
214
65
469
247
297
171
237
649
314
402
519
157
1...

output:

? 487 489
? 503 112
? 986 752
? 667 955
? 919 758
? 899 699
? 966 431
? 171 827
? 347 611
? 393 271
? 264 576
? 116 111
? 150 930
? 444 233
? 707 631
? 118 578
? 753 952
? 863 310
? 647 897
? 501 454
? 326 20
? 97 997
? 7 265
? 732 890
? 493 804
? 372 255
? 195 75
? 398 421
? 350 671
? 567 424
? 798...

result:

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

Test #85:

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

input:

1000
653
43
326
131
493
619
141
230
236
339
474
72
133
67
405
29
208
49
603
214
590
772
152
632
599
367
243
111
22
348
200
185
239
399
303
340
322
305
90
183
41
187
177
97
238
55
263
126
498
411
569
293
46
893
118
181
257
509
92
826
320
57
446
290
146
254
471
668
453
547
949
552
5
110
108
12
17
192
...

output:

? 934 653
? 78 43
? 985 326
? 483 131
? 493 534
? 619 999
? 382 141
? 230 602
? 338 236
? 354 339
? 474 877
? 109 72
? 395 133
? 67 501
? 618 405
? 626 29
? 208 840
? 244 49
? 770 603
? 762 214
? 929 590
? 910 772
? 152 249
? 785 632
? 599 750
? 367 637
? 243 918
? 251 111
? 907 22
? 348 594
? 200 2...

result:

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

Test #86:

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

input:

1000
171
17
903
439
188
136
38
696
484
481
467
284
239
40
127
83
735
443
202
336
279
453
828
221
770
363
376
37
298
816
543
559
4
621
190
137
293
370
235
656
67
223
222
8
242
428
158
356
23
339
456
88
478
564
612
216
141
639
358
108
5
388
124
234
79
244
432
207
273
637
762
435
133
230
18
557
885
130...

output:

? 654 171
? 587 17
? 968 903
? 439 674
? 188 573
? 136 957
? 852 38
? 952 696
? 484 658
? 481 634
? 623 467
? 394 284
? 918 239
? 40 353
? 521 127
? 982 83
? 802 735
? 443 482
? 582 202
? 336 819
? 670 279
? 453 922
? 879 828
? 679 221
? 861 770
? 998 363
? 376 575
? 37 954
? 298 465
? 926 816
? 543...

result:

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

Test #87:

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

input:

1000
365
22
343
191
192
383
333
128
637
496
10
428
32
245
590
565
164
55
480
214
556
268
211
221
52
561
124
85
17
187
322
292
435
110
484
3
114
310
693
394
787
950
390
273
271
337
235
362
505
180
127
497
311
19
16
438
853
651
666
28
305
780
48
336
138
99
629
617
167
453
848
49
18
478
101
89
412
885
...

output:

? 365 672
? 22 321
? 752 343
? 191 907
? 192 829
? 383 838
? 369 333
? 128 924
? 637 822
? 496 892
? 10 405
? 514 428
? 32 423
? 245 461
? 590 784
? 565 581
? 164 671
? 286 55
? 824 480
? 214 397
? 609 556
? 710 268
? 211 487
? 625 221
? 52 805
? 561 808
? 458 124
? 339 85
? 733 17
? 513 187
? 809 3...

result:

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

Subtask #3:

score: 32.3822
Acceptable Answer

Test #88:

score: 33.3309
Acceptable Answer
time: 7ms
memory: 12664kb

input:

1500
502
917
726
745
813
319
723
131
252
49
1037
587
421
504
461
72
52
516
952
533
3
9
177
1147
200
147
1219
277
481
814
76
925
366
700
681
196
716
444
508
551
887
113
61
287
915
1072
746
781
1042
1366
494
1282
586
414
645
369
1001
189
1023
291
60
428
694
221
181
967
763
537
32
892
854
95
908
26
109...

output:

? 673 502
? 917 1419
? 726 940
? 745 850
? 813 1367
? 319 1096
? 1162 723
? 759 131
? 316 252
? 49 784
? 1390 1037
? 587 611
? 421 1080
? 504 1446
? 1322 461
? 1494 72
? 52 225
? 969 516
? 1158 952
? 737 533
? 3 27
? 9 416
? 177 1319
? 1492 1147
? 223 200
? 926 147
? 1219 1240
? 647 277
? 740 481
? ...

result:

points 0.41663671490 points  0.41663671490 n = 1500, you used 2679 queries

Test #89:

score: 33.4537
Acceptable Answer
time: 9ms
memory: 12792kb

input:

1500
614
805
287
1106
132
139
238
487
816
329
1004
170
218
790
827
716
1005
899
434
1128
128
488
416
154
399
1272
525
413
240
552
393
341
112
655
88
373
1028
746
778
836
387
1065
495
875
949
439
545
465
357
305
633
53
448
291
486
678
636
123
475
346
44
631
310
474
241
25
51
395
671
70
644
280
86
872...

output:

? 398 887
? 696 95
? 540 1214
? 301 395
? 1369 207
? 310 1362
? 1044 1263
? 1014 866
? 685 658
? 493 1172
? 497 131
? 1099 1331
? 1283 589
? 129 711
? 674 317
? 645 785
? 496 433
? 241 602
? 812 1067
? 373 335
? 1373 1358
? 630 1013
? 424 1085
? 404 1347
? 1102 953
? 229 128
? 976 762
? 1088 714
? 1...

result:

points 0.41817125520 points  0.41817125520 n = 1500, you used 2667 queries

Test #90:

score: 33.4229
Acceptable Answer
time: 6ms
memory: 12624kb

input:

1500
290
288
1240
409
155
287
82
58
574
610
1195
422
15
593
386
675
132
60
39
480
745
1032
347
474
805
570
519
90
677
237
469
654
49
839
644
843
589
528
998
711
415
348
613
271
612
221
14
256
205
23
489
28
431
631
210
667
446
953
1001
562
298
208
791
553
245
1175
156
286
1133
859
272
380
31
378
1298...

output:

? 1356 1183
? 1357 665
? 881 706
? 205 878
? 78 484
? 635 144
? 783 1460
? 1199 1472
? 1214 922
? 1196 709
? 598 631
? 793 1290
? 8 159
? 297 401
? 199 1308
? 638 338
? 1435 700
? 1471 937
? 20 1065
? 335 1261
? 844 373
? 985 938
? 814 174
? 1264 741
? 481 403
? 1092 1216
? 538 260
? 690 1456
? 339 ...

result:

points 0.41778614580 points  0.41778614580 n = 1500, you used 2670 queries

Test #91:

score: 33.7451
Acceptable Answer
time: 8ms
memory: 12820kb

input:

1500
351
1117
561
350
79
890
254
699
496
312
99
55
192
783
87
1102
170
553
1204
82
90
951
186
6
120
234
101
755
846
394
1134
258
388
183
286
1125
475
1124
248
213
115
238
277
322
1104
748
200
89
521
636
434
1105
1305
473
440
961
457
504
885
720
142
145
888
880
1021
599
401
605
1320
802
22
245
38
818...

output:

? 233 1325
? 942 619
? 1220 755
? 175 428
? 1461 1048
? 976 445
? 1190 127
? 472 1151
? 248 351
? 580 156
? 1451 55
? 1116 1473
? 96 426
? 1109 851
? 1086 1457
? 551 860
? 85 1202
? 1224 684
? 735 602
? 1380 41
? 45 113
? 861 1025
? 1010 93
? 3 702
? 381 60
? 1265 117
? 1450 315
? 762 1123
? 655 423...

result:

points 0.42181410550 points  0.42181410550 n = 1500, you used 2639 queries

Test #92:

score: 33.0692
Acceptable Answer
time: 0ms
memory: 12576kb

input:

1500
376
159
414
563
438
218
457
37
724
544
1258
874
783
633
399
347
614
471
632
315
371
298
852
63
928
884
49
1021
131
656
1087
1054
153
712
270
173
607
236
71
226
186
714
406
933
776
269
458
879
166
434
520
977
201
348
232
309
125
8
1125
1073
481
515
313
442
357
599
1133
744
821
675
828
526
785
11...

output:

? 1038 563
? 830 272
? 544 84
? 1389 1032
? 1421 532
? 642 879
? 85 979
? 769 113
? 290 389
? 366 479
? 1426 122
? 314 1348
? 1142 216
? 1269 1067
? 950 1329
? 8 924
? 444 1210
? 388 986
? 1472 435
? 1475 908
? 936 355
? 1408 602
? 1499 325
? 782 1106
? 287 1225
? 309 230
? 775 550
? 1261 57
? 816 5...

result:

points 0.41336477310 points  0.41336477310 n = 1500, you used 2705 queries

Test #93:

score: 32.4956
Acceptable Answer
time: 0ms
memory: 12788kb

input:

1500
249
1088
159
807
294
80
1114
693
385
643
648
55
398
1057
1123
361
157
100
152
500
231
502
359
27
711
685
303
766
139
457
521
900
401
880
7
775
1060
662
12
107
586
606
243
146
568
207
44
1053
888
334
403
535
445
150
1021
202
672
163
315
370
96
111
1122
609
418
87
84
468
185
463
278
464
968
536
2...

output:

? 1471 626
? 1294 1393
? 12 671
? 347 1204
? 564 897
? 387 790
? 1307 23
? 404 322
? 1430 558
? 1161 429
? 1494 1074
? 329 723
? 949 203
? 138 222
? 189 1478
? 570 1088
? 263 672
? 800 1114
? 1423 826
? 1126 1000
? 393 635
? 1246 1001
? 571 998
? 737 1267
? 315 395
? 408 233
? 360 599
? 1479 1133
? ...

result:

points 0.40619451380 points  0.40619451380 n = 1500, you used 2764 queries

Test #94:

score: 33.0096
Acceptable Answer
time: 4ms
memory: 12660kb

input:

1500
1095
48
478
952
45
26
793
320
801
751
319
443
496
363
842
1352
887
831
91
487
634
364
223
1280
505
171
455
983
19
119
631
279
722
1073
379
311
437
670
479
1148
467
93
974
771
653
732
301
1076
802
21
744
743
338
32
276
114
555
879
868
387
303
34
107
757
673
166
869
711
245
139
899
1015
916
782
3...

output:

? 690 1290
? 1405 81
? 545 1368
? 1208 404
? 1411 1369
? 1449 432
? 856 86
? 861 1058
? 102 462
? 2 658
? 427 863
? 615 66
? 844 509
? 884 775
? 664 184
? 1204 1404
? 274 296
? 162 902
? 1100 1319
? 337 527
? 233 28
? 1402 773
? 1055 765
? 1060 1350
? 464 491
? 770 1159
? 1194 591
? 824 466
? 1463 1...

result:

points 0.41261973850 points  0.41261973850 n = 1500, you used 2711 queries

Test #95:

score: 32.6388
Acceptable Answer
time: 0ms
memory: 12860kb

input:

1500
448
980
385
956
435
149
428
271
429
657
194
280
842
4
226
311
668
476
1035
90
2
195
1059
46
264
485
326
40
223
142
65
1331
393
605
484
320
59
432
860
625
1107
1213
130
131
41
297
141
294
124
467
165
322
202
480
824
1054
168
233
208
723
861
87
1138
51
121
557
251
354
981
540
209
641
18
89
206
29...

output:

? 896 439
? 1041 739
? 770 1091
? 507 1089
? 155 870
? 298 1330
? 1377 856
? 542 1096
? 119 858
? 245 1314
? 388 573
? 1258 560
? 1199 1317
? 78 8
? 1292 452
? 1227 622
? 1336 851
? 952 389
? 185 931
? 180 1471
? 1052 4
? 390 1430
? 139 883
? 378 92
? 682 528
? 970 1455
? 652 1429
? 356 80
? 1473 44...

result:

points 0.40798522350 points  0.40798522350 n = 1500, you used 2749 queries

Test #96:

score: 32.5622
Acceptable Answer
time: 0ms
memory: 12564kb

input:

1500
663
90
129
320
92
60
698
914
50
512
284
857
399
533
278
656
563
790
107
72
78
956
1071
765
889
482
288
376
543
55
558
98
82
245
598
761
1158
738
1174
339
54
58
534
80
757
920
1014
510
758
49
426
859
283
610
480
866
1112
1097
1058
101
882
67
560
628
21
305
1018
286
638
1057
985
152
292
402
361
6...

output:

? 662 1200
? 91 865
? 128 1138
? 1022 321
? 937 93
? 61 1423
? 699 833
? 1248 915
? 51 522
? 513 1174
? 1145 285
? 856 992
? 398 934
? 532 962
? 1415 279
? 889 657
? 825 562
? 791 1347
? 1437 106
? 73 669
? 1312 79
? 957 1477
? 1070 1213
? 764 965
? 888 1363
? 906 483
? 289 887
? 377 1050
? 1308 542...

result:

points 0.40702751870 points  0.40702751870 n = 1500, you used 2757 queries

Test #97:

score: 33.1391
Acceptable Answer
time: 5ms
memory: 12692kb

input:

1500
495
1133
185
267
1015
233
710
571
655
389
268
1040
1196
844
276
1006
293
60
287
311
540
232
634
552
25
1168
241
555
335
1224
872
1306
501
632
883
967
306
210
69
33
554
1022
82
264
435
133
330
236
600
475
1163
382
452
517
808
731
42
1111
284
563
964
941
458
24
2
401
1344
770
1355
1470
52
101
112...

output:

? 1007 551
? 369 10
? 421 1317
? 1235 1085
? 487 95
? 877 1269
? 787 790
? 366 931
? 702 847
? 648 1113
? 1232 165
? 359 460
? 304 23
? 656 141
? 1224 1222
? 232 494
? 310 1209
? 1440 171
? 40 1215
? 992 1191
? 98 960
? 1268 381
? 80 866
? 433 948
? 1087 1477
? 240 332
? 1157 1261
? 947 173
? 1167 5...

result:

points 0.41423868320 points  0.41423868320 n = 1500, you used 2698 queries

Test #98:

score: 33.7662
Acceptable Answer
time: 0ms
memory: 12628kb

input:

1500
174
462
460
732
262
936
338
101
187
18
303
806
482
713
491
898
329
825
20
643
264
277
190
90
369
219
247
512
169
697
71
1140
1
196
808
269
7
94
343
523
276
234
356
431
279
496
618
738
595
225
648
119
644
48
1238
36
148
866
204
944
949
472
17
867
255
689
752
132
484
1351
108
315
257
640
479
80
1...

output:

? 1010 704
? 2 1044
? 383 375
? 765 568
? 667 980
? 823 136
? 1 203
? 341 1314
? 1330 88
? 319 54
? 71 646
? 1262 1430
? 81 806
? 1417 1062
? 992 235
? 649 320
? 283 268
? 515 952
? 451 1168
? 109 1318
? 1004 767
? 857 382
? 756 999
? 1103 1497
? 1279 1070
? 1455 708
? 1121 691
? 430 877
? 1052 890
...

result:

points 0.42207772590 points  0.42207772590 n = 1500, you used 2637 queries

Test #99:

score: 33.9792
Acceptable Answer
time: 0ms
memory: 12820kb

input:

1500
306
343
549
718
188
482
1013
554
915
477
151
54
506
962
510
132
578
156
490
1149
558
1084
227
797
128
1030
639
34
628
321
721
884
348
204
130
583
314
57
820
1405
8
461
839
846
219
444
738
615
956
149
850
378
664
748
1120
694
1145
452
64
49
665
92
171
550
1129
701
1202
1134
443
165
681
138
1002
...

output:

? 1256 608
? 326 1467
? 850 302
? 444 228
? 239 538
? 1008 584
? 661 925
? 784 473
? 292 18
? 1046 603
? 406 711
? 218 620
? 429 170
? 992 1484
? 1350 32
? 1363 674
? 943 634
? 781 447
? 269 835
? 252 548
? 452 625
? 423 125
? 153 1048
? 489 758
? 1110 1075
? 146 1404
? 748 1162
? 891 825
? 192 204
...

result:

points 0.42473973010 points  0.42473973010 n = 1500, you used 2617 queries

Test #100:

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

input:

1500
355
1260
776
770
114
530
849
454
23
524
103
49
216
383
396
940
60
363
113
485
35
478
495
699
1096
45
20
223
82
1063
176
262
643
367
208
275
244
1371
43
234
858
595
38
1055
1065
304
263
734
271
1025
435
773
578
326
357
59
1168
259
112
93
484
165
564
440
1336
1093
89
637
44
47
136
308
519
31
231
...

output:

? 1259 850
? 192 69
? 80 68
? 51 299
? 1125 474
? 202 1195
? 812 360
? 626 337
? 734 1458
? 892 1054
? 1179 138
? 321 1330
? 789 1286
? 1449 1212
? 601 1159
? 300 1130
? 747 23
? 336 86
? 865 686
? 494 745
? 72 1049
? 119 847
? 1232 238
? 828 327
? 251 304
? 523 595
? 665 859
? 951 1005
? 1378 1273
...

result:

points 0.42380264540 points  0.42380264540 n = 1500, you used 2624 queries

Test #101:

score: 33.5362
Acceptable Answer
time: 10ms
memory: 12628kb

input:

1500
1970
847
1144
16
1181
784
1202
1298
67
248
1450
310
2104
68
181
171
1357
818
1056
77
1874
529
694
265
1107
981
1595
304
299
318
1000
29
1006
2263
462
1435
1568
575
23
843
1277
520
965
886
91
1317
48
2484
432
836
1371
691
652
1245
149
51
612
1326
406
969
615
9
427
1208
849
880
269
2363
1484
974
...

output:

? 1152 980
? 418 1321
? 572 1190
? 1500 8
? 1062 590
? 506 381
? 599 1458
? 648 1481
? 35 1291
? 124 1327
? 1354 727
? 155 894
? 1483 1047
? 988 36
? 91 1015
? 308 87
? 777 679
? 400 507
? 608 528
? 38 907
? 1427 939
? 880 261
? 508 343
? 1294 132
? 561 550
? 484 871
? 915 802
? 1389 153
? 151 1335
...

result:

points 0.41920307350 points  0.41920307350 n = 1500, you used 2659 queries

Test #102:

score: 33.3819
Acceptable Answer
time: 3ms
memory: 12572kb

input:

1500
85251
85185
85186
85061
85987
85089
85563
84986
85454
85207
85147
85348
84982
84950
85320
84974
86167
86053
85217
85109
85591
85137
85844
85369
86107
84942
86069
85914
85375
85544
84999
85783
85673
85014
85321
85290
84920
84905
85034
85118
85714
85029
85234
85332
85090
84917
85133
85396
85754
8...

output:

? 768 352
? 286 382
? 287 700
? 162 450
? 1480 1087
? 190 678
? 663 838
? 87 1301
? 948 554
? 308 1004
? 1283 248
? 448 752
? 455 83
? 51 845
? 750 420
? 75 1163
? 1267 1406
? 1294 1153
? 442 318
? 210 1173
? 1109 691
? 785 238
? 1321 944
? 469 1182
? 1207 1418
? 43 661
? 1169 1428
? 1323 1014
? 475...

result:

points 0.41727419990 points  0.41727419990 n = 1500, you used 2674 queries

Test #103:

score: 32.687
Acceptable Answer
time: 7ms
memory: 12620kb

input:

1500
8931
6078
6897
7032
5115
6117
6631
5706
6380
8267
6201
7872
6306
5092
5032
6075
5188
7484
5691
7314
5212
7815
6154
6013
6094
6592
5147
6680
6570
6012
8147
5903
5880
5352
7143
6403
6189
5191
8231
6550
5685
6946
5512
5781
9246
5321
5807
8336
5033
6031
6989
6207
6574
7293
6043
5102
6762
5715
6334
...

output:

? 1193 1199
? 1470 326
? 590 675
? 806 635
? 1110 33
? 1485 338
? 1165 515
? 393 213
? 1397 431
? 1009 1254
? 367 689
? 1161 886
? 401 1057
? 609 25
? 12 625
? 325 681
? 133 56
? 761 1471
? 1045 208
? 1146 719
? 68 1158
? 866 1480
? 351 389
? 619 312
? 331 1062
? 1244 502
? 41 532
? 525 1055
? 1223 ...

result:

points 0.4085869090 points  0.4085869090 n = 1500, you used 2744 queries

Test #104:

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

input:

1500
4464
5703
4416
5001
4059
4529
4930
4759
4540
4114
4315
4389
4685
5434
4174
4920
4959
5101
4643
4238
5143
4044
5641
4458
4813
4073
4837
4269
5057
4518
4470
4136
4952
5457
4688
5408
4737
4680
4257
4666
5663
5599
4545
5601
5016
4338
4420
4154
4220
5207
4750
4047
4886
4751
4671
4525
4009
5301
4731
...

output:

? 355 670
? 1360 1271
? 319 386
? 751 1289
? 48 376
? 432 400
? 1484 694
? 576 1158
? 436 409
? 477 90
? 1200 246
? 300 1397
? 1206 519
? 1385 1070
? 1414 136
? 744 684
? 1378 719
? 829 1043
? 517 485
? 735 186
? 863 999
? 36 668
? 1220 1418
? 351 654
? 1071 612
? 59 1424
? 627 1284
? 1500 212
? 138...

result:

points 0.42813507660 points  0.42813507660 n = 1500, you used 2592 queries

Test #105:

score: 33.3717
Acceptable Answer
time: 3ms
memory: 12696kb

input:

1500
66210
52704
62901
63118
63331
63240
56064
55925
68328
71064
60352
50483
70751
70399
67218
50084
52101
50599
50256
67699
64504
55496
53863
57631
60743
54043
53142
59556
58605
54507
51355
61663
56898
55357
60843
64195
59648
50965
65511
52207
80553
56742
76632
83400
72457
71185
60158
50363
60069
5...

output:

? 942 697
? 131 1357
? 543 1471
? 1464 552
? 564 717
? 758 561
? 280 1220
? 619 275
? 1452 790
? 1405 909
? 452 765
? 1121 31
? 896 929
? 872 1026
? 1070 741
? 1127 5
? 104 163
? 42 943
? 136 13
? 761 1077
? 628 753
? 930 253
? 182 1115
? 342 1238
? 470 1262
? 997 194
? 1071 152
? 425 813
? 388 1397...

result:

points 0.4171464860 points  0.4171464860 n = 1500, you used 2675 queries

Test #106:

score: 33.6298
Acceptable Answer
time: 4ms
memory: 12572kb

input:

1500
413
335
537
410
464
756
139
469
326
528
955
696
1
1151
254
308
1166
1172
750
717
426
643
55
634
101
215
856
541
165
1013
352
59
138
399
340
203
134
1139
324
472
958
256
122
199
150
225
23
347
36
629
665
92
1098
301
706
35
572
829
969
131
429
45
827
487
1115
748
226
356
723
205
811
854
588
668
1...

output:

? 1341 754
? 853 537
? 553 1046
? 1409 505
? 77 737
? 905 81
? 1474 434
? 438 776
? 125 1029
? 850 48
? 881 117
? 1304 642
? 472 1370
? 255 345
? 277 675
? 556 416
? 67 18
? 122 982
? 1112 785
? 570 715
? 1345 1395
? 1269 446
? 1295 864
? 979 420
? 495 773
? 827 987
? 968 1054
? 1140 312
? 727 265
?...

result:

points 0.42037241680 points  0.42037241680 n = 1500, you used 2650 queries

Test #107:

score: 33.8829
Acceptable Answer
time: 10ms
memory: 12688kb

input:

1500
592
1047
560
233
1146
142
94
997
776
498
64
297
301
41
712
139
36
789
1203
667
821
1077
489
946
1337
1168
639
963
287
59
1330
205
514
1371
676
1313
70
124
945
765
196
367
835
1223
1316
433
373
651
1558
401
1350
1134
421
111
702
653
67
971
317
792
475
771
362
915
1202
540
629
83
863
1247
79
377
...

output:

? 543 1212
? 631 829
? 328 566
? 830 733
? 466 609
? 109 971
? 1025 655
? 965 861
? 1011 26
? 326 198
? 1266 949
? 999 1273
? 189 237
? 1290 764
? 411 1459
? 715 975
? 904 96
? 548 400
? 627 1120
? 21 412
? 634 1444
? 1305 215
? 1354 1164
? 849 606
? 268 1013
? 1408 91
? 131 1390
? 1242 105
? 316 40...

result:

points 0.42353597870 points  0.42353597870 n = 1500, you used 2626 queries

Test #108:

score: 33.8829
Acceptable Answer
time: 3ms
memory: 12860kb

input:

1500
85131
84992
85219
85772
85037
85884
84991
85457
85164
85321
85009
86219
85135
85856
85295
84928
86163
85128
85057
85090
85045
85016
85638
85157
85026
85130
85717
85384
85116
85032
85982
84943
84920
85625
85114
84958
86210
85013
85419
85003
85342
85589
85299
85415
85313
85235
85466
85119
85948
8...

output:

? 953 900
? 479 838
? 1413 1467
? 90 544
? 901 1328
? 1086 305
? 246 912
? 57 801
? 825 1253
? 279 585
? 13 1070
? 1289 580
? 1065 30
? 1434 559
? 755 536
? 151 1459
? 222 1304
? 1020 408
? 607 884
? 758 1469
? 596 427
? 1133 515
? 265 566
? 1388 737
? 212 558
? 656 867
? 234 258
? 419 997
? 681 719...

result:

points 0.42353597870 points  0.42353597870 n = 1500, you used 2626 queries

Test #109:

score: 34.033
Acceptable Answer
time: 3ms
memory: 12624kb

input:

1500
6897
8258
8237
5949
7050
6118
7120
6075
6817
7002
7049
9347
5311
7715
5318
5192
5162
6004
6599
5746
6467
8639
5056
6649
6674
5443
6178
5754
6341
6215
7625
7667
5607
7578
5505
7482
8381
7089
8203
6071
6335
5258
8416
6778
5177
7530
5837
8443
5434
7017
5359
5173
5295
8168
6404
8156
7459
8745
9115
...

output:

? 155 1468
? 811 931
? 1126 1026
? 78 1151
? 1098 1452
? 764 1233
? 1296 506
? 627 551
? 805 103
? 780 1192
? 381 416
? 55 1095
? 645 298
? 119 1122
? 608 168
? 654 1444
? 27 279
? 1041 437
? 36 345
? 1385 87
? 554 621
? 1487 145
? 1392 594
? 1021 393
? 140 698
? 536 45
? 1017 821
? 590 312
? 206 12...

result:

points 0.42541267880 points  0.42541267880 n = 1500, you used 2612 queries

Test #110:

score: 33.3513
Acceptable Answer
time: 9ms
memory: 12600kb

input:

1500
4185
4731
4845
5043
4376
5099
4922
5146
5797
4072
5361
4510
4681
4184
4145
4442
5158
4436
4776
4074
4794
4403
4057
4160
4030
4663
4144
4320
4290
5491
4124
4325
4227
5115
4718
4119
4230
4667
4545
4419
5205
4064
5042
4501
4589
4281
4176
4401
4711
4846
4952
4649
5779
4787
4709
4106
4912
4404
4001
...

output:

? 505 760
? 339 774
? 681 931
? 172 372
? 679 724
? 740 335
? 261 1420
? 691 189
? 1221 181
? 380 371
? 1192 8
? 230 1477
? 967 1306
? 951 829
? 555 1060
? 908 476
? 246 685
? 635 213
? 1405 228
? 544 1324
? 1462 1267
? 831 1367
? 1499 697
? 641 1155
? 922 780
? 673 236
? 812 1000
? 39 885
? 387 212...

result:

points 0.41689138390 points  0.41689138390 n = 1500, you used 2677 queries

Test #111:

score: 33.6611
Acceptable Answer
time: 6ms
memory: 12688kb

input:

1500
60904
53486
61859
58117
53383
55245
52812
68158
52326
58267
65586
73126
63676
60141
77095
52359
67518
78193
65988
57996
50476
58374
56473
59695
72488
55582
65466
57395
57951
72672
81223
56566
60478
65895
64463
80338
64263
77587
78697
59859
59337
65850
65011
72497
50771
67209
84583
65414
62919
5...

output:

? 1375 790
? 750 1250
? 449 1266
? 1214 1192
? 1022 709
? 489 1255
? 579 557
? 1225 593
? 544 1067
? 1246 347
? 704 943
? 420 394
? 962 322
? 684 225
? 407 165
? 648 794
? 582 1419
? 250 122
? 761 327
? 1475 472
? 1295 589
? 1203 76
? 248 473
? 197 18
? 922 1257
? 260 1251
? 678 1360
? 611 416
? 414...

result:

points 0.42076423240 points  0.42076423240 n = 1500, you used 2647 queries

Test #112:

score: 33.9149
Acceptable Answer
time: 0ms
memory: 12628kb

input:

1500
557
316
114
476
380
97
986
1120
104
419
337
850
427
336
58
1128
345
1163
77
629
41
655
87
574
377
649
334
765
302
521
330
269
163
93
128
475
662
133
617
591
101
823
27
438
636
322
657
203
217
176
1106
985
667
1143
1233
483
406
136
245
303
122
1023
742
335
71
233
22
604
296
218
145
247
304
1272
...

output:

? 557 1004
? 1132 316
? 973 114
? 476 755
? 954 380
? 97 1055
? 1224 986
? 1120 1476
? 888 104
? 419 1384
? 337 593
? 1064 850
? 484 427
? 336 666
? 1319 58
? 1128 1442
? 1354 345
? 1376 1163
? 947 77
? 629 1012
? 41 757
? 655 700
? 1007 87
? 1424 574
? 377 1303
? 649 1390
? 334 623
? 944 765
? 1306...

result:

points 0.42393615680 points  0.42393615680 n = 1500, you used 2623 queries

Test #113:

score: 33.0592
Acceptable Answer
time: 3ms
memory: 12624kb

input:

1500
941
618
570
1289
228
198
898
487
671
317
101
942
491
224
253
114
904
718
775
537
1047
419
177
555
166
614
123
271
610
641
110
333
336
1229
34
429
1264
588
104
100
847
750
221
433
534
948
1041
436
462
1201
466
861
340
640
856
40
1124
145
617
25
181
523
288
620
681
55
365
239
237
1064
779
1179
53...

output:

? 941 1138
? 1070 618
? 752 570
? 1290 1289
? 228 1355
? 198 1219
? 898 1353
? 896 487
? 671 831
? 317 440
? 1419 101
? 942 1000
? 727 491
? 224 1007
? 993 253
? 114 720
? 913 904
? 718 1115
? 916 775
? 537 998
? 1204 1047
? 1097 419
? 177 1141
? 1276 555
? 166 363
? 1443 614
? 123 1399
? 271 1224
?...

result:

points 0.41324034340 points  0.41324034340 n = 1500, you used 2706 queries

Test #114:

score: 33.5466
Acceptable Answer
time: 0ms
memory: 12784kb

input:

1500
7
903
698
519
593
795
702
633
112
226
174
30
298
1181
201
877
937
248
181
443
885
908
565
182
341
246
792
781
1015
179
343
707
1247
694
249
131
1170
691
529
739
971
700
68
600
651
260
552
1141
31
238
1284
63
1043
162
251
854
815
657
216
12
879
1127
778
1346
33
737
217
1199
76
639
237
851
202
38...

output:

? 1280 20
? 840 188
? 106 314
? 1188 593
? 763 367
? 1133 177
? 568 832
? 233 154
? 441 754
? 814 912
? 1175 1106
? 600 516
? 174 1149
? 1475 78
? 1125 193
? 1004 583
? 218 1274
? 1383 1043
? 1486 1330
? 559 145
? 1094 1109
? 1093 1282
? 783 1019
? 1344 227
? 1320 859
? 594 1183
? 1263 343
? 339 846...

result:

points 0.41933255130 points  0.41933255130 n = 1500, you used 2658 queries

Test #115:

score: 33.5362
Acceptable Answer
time: 0ms
memory: 12660kb

input:

1500
71
556
1167
52
661
21
847
513
439
920
888
193
241
382
836
445
491
484
403
324
301
164
17
395
1203
347
598
611
227
428
982
1057
883
212
1149
54
694
279
210
1376
297
805
138
199
828
741
282
802
118
745
595
214
24
82
106
821
616
861
530
137
800
812
11
947
140
501
249
822
677
1084
909
157
4
112
200...

output:

? 194 71
? 556 1039
? 1167 1403
? 52 1242
? 1002 661
? 21 645
? 1122 847
? 1114 513
? 704 439
? 1384 920
? 946 888
? 193 901
? 859 241
? 729 382
? 1286 836
? 445 1014
? 1193 491
? 646 484
? 403 1404
? 324 1224
? 553 301
? 164 1478
? 17 993
? 478 395
? 1309 1203
? 631 347
? 598 1212
? 1407 611
? 1405...

result:

points 0.41920307350 points  0.41920307350 n = 1500, you used 2659 queries

Test #116:

score: 33.3819
Acceptable Answer
time: 8ms
memory: 12572kb

input:

1500
42
892
674
1281
384
61
402
154
1227
881
98
616
50
364
790
1073
940
516
289
390
1
37
692
690
530
121
525
65
316
631
73
563
36
500
105
1075
48
1323
198
39
452
165
55
504
762
264
368
793
645
571
601
587
798
954
893
825
942
20
750
689
1127
1203
257
551
542
286
517
835
686
826
188
122
830
1008
442
1...

output:

? 42 1479
? 892 1045
? 1232 674
? 1281 1459
? 575 384
? 1188 61
? 458 402
? 154 1480
? 1291 1227
? 1495 881
? 1030 98
? 616 688
? 999 50
? 364 620
? 790 932
? 1073 1280
? 940 1198
? 609 516
? 289 1216
? 390 933
? 1499 1382
? 37 1118
? 701 692
? 690 863
? 530 1186
? 420 121
? 580 525
? 65 624
? 316 1...

result:

points 0.41727419990 points  0.41727419990 n = 1500, you used 2674 queries

Test #117:

score: 32.3822
Acceptable Answer
time: 0ms
memory: 12852kb

input:

1500
387
770
249
581
618
372
612
453
409
74
1077
705
1065
422
620
741
73
470
550
247
354
121
892
1071
650
640
1320
493
937
320
386
254
1051
396
1045
275
1342
1087
293
506
1315
1005
110
399
134
525
333
538
95
83
948
23
1106
767
1036
556
488
1235
898
430
211
690
1035
786
87
258
924
229
691
1076
314
4
...

output:

? 387 1174
? 879 770
? 617 249
? 1284 581
? 618 1068
? 1120 372
? 612 1061
? 889 453
? 409 1422
? 74 559
? 1077 1146
? 705 1453
? 1065 1305
? 422 473
? 620 1401
? 1425 741
? 439 73
? 1249 470
? 750 550
? 247 1153
? 354 821
? 831 121
? 1438 892
? 1071 1214
? 650 1491
? 640 971
? 1320 1375
? 493 1107
...

result:

points 0.40477718040 points  0.40477718040 n = 1500, you used 2776 queries