QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765487#8267. Staring Contest_8_8_#51.175353 15ms12948kbC++204.1kb2024-11-20 14:25:532024-11-20 14:25:53

Judging History

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

  • [2024-11-20 14:25:53]
  • 评测
  • 测评结果:51.175353
  • 用时:15ms
  • 内存:12948kb
  • [2024-11-20 14:25:53]
  • 提交

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) {
        f.push_back({get(x[i], x[i + 1]), x[i], x[i + 1]});
    }
    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(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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9
Accepted

Test #1:

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

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: 2ms
memory: 12580kb

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: 2ms
memory: 12520kb

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

input:

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

output:

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

result:

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

Test #5:

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

input:

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

output:

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

result:

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

Test #6:

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

input:

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

output:

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

result:

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

Test #7:

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

input:

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

output:

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

result:

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

Test #8:

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

input:

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

output:

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

result:

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

Test #9:

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

input:

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

output:

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

result:

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

Test #10:

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

input:

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

output:

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

result:

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

Test #11:

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

input:

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

output:

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

result:

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

Test #12:

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

input:

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

output:

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

result:

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

Test #13:

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

input:

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

output:

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

result:

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

Test #14:

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

input:

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

output:

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

result:

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

Test #15:

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

input:

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

output:

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

result:

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

Test #16:

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

input:

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

output:

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

result:

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

Test #17:

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

input:

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

output:

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

result:

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

Test #18:

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

input:

50
86352
86373
86369
86392
86385
86357
86366
86376
86365
86362
86355
86350
86354
86374
86389
86359
86377
86378
86379
86384
86353
86351
86358
86383
86364
86375
86358
86356
86353
86383
86379
86395
86396
86359
86397
86380
86372
86368
86355
86362
86365
86376
86366
86360
86385
86392
86369
86373
86367
863...

output:

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

result:

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

Test #19:

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

input:

50
8428
5813
5703
6109
7026
9032
7060
6476
7663
6375
7560
6824
5773
6926
7993
7779
5076
8526
6767
5914
6099
5302
6297
7174
5406
9258
6297
5302
8098
5914
8947
8878
6651
7779
7993
7563
7159
8878
8060
6375
8878
6476
7060
8878
9404
8143
9404
8464
8428
9838
9032
8939
8883
8198
8098
8006
7233
6651
7159
75...

output:

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

result:

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

Test #20:

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

input:

50
5036
5033
5041
5051
5003
5046
5085
5025
5049
5004
5035
5031
5054
5021
5024
5039
5073
5000
5027
5005
5010
5069
5017
5038
5062
5038
5050
5062
5078
5005
5082
5052
5073
5072
5030
5021
5054
5086
5075
5059
5083
5025
5085
5048
5023
5086
5066
5084
5036
5096
5084
5082
5078
5075
5069
5066
5064
5058
5050
50...

output:

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

result:

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

Test #21:

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

input:

50
50293
61154
58019
56991
52391
57364
51290
56501
67289
56134
67305
53250
68459
70252
52604
70891
75331
54962
52428
57154
50918
78428
67638
66090
68114
68114
69824
69824
58109
77305
78428
54962
75331
73709
73709
70252
68459
53250
67305
56134
73709
60767
51290
57364
52391
73709
62431
61154
50293
823...

output:

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

result:

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

Test #22:

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

input:

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

output:

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

result:

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

Test #23:

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

input:

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

output:

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

result:

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

Test #24:

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

input:

50
86365
86354
86377
86364
86360
86356
86358
86355
86385
86367
86388
86392
86378
86373
86369
86375
86370
86357
86359
86353
86351
86366
86362
86363
86350
86363
86380
86366
86352
86376
86359
86357
86381
86395
86369
86373
86378
86395
86397
86367
86385
86391
86399
86361
86371
86383
86382
86354
86387
863...

output:

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

result:

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

Test #25:

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

input:

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

output:

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

result:

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

Test #26:

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

input:

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

output:

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

result:

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

Test #27:

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

input:

50
68422
58717
76101
61968
53213
61401
67069
71272
66448
67146
51658
72987
53987
72291
54250
54630
62248
73863
76671
70576
58357
58746
53454
72620
55504
72585
53454
58746
58357
70576
72620
76671
62248
57318
65477
72291
53987
72987
73081
70928
66448
78154
67069
61401
53213
61968
76101
58717
68422
725...

output:

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

result:

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

Test #28:

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

input:

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

output:

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

result:

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

Test #29:

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

input:

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

output:

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

result:

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

Test #30:

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

input:

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

output:

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

result:

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

Test #31:

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

input:

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

output:

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

result:

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

Test #32:

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

input:

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

output:

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

result:

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

Test #33:

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

input:

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

output:

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

result:

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

Test #34:

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

input:

4
3
2
5
3

output:

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

input:

4
2
3
2
3
5

output:

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

result:

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

Test #36:

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

input:

4
3
2
2
3
5

output:

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

input:

4
3
2
3
2
5

output:

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

input:

4
2
5
2
3
3

output:

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

input:

4
2
5
2
3

output:

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

result:

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

Test #40:

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

input:

4
2
5
2
3

output:

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

result:

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

Test #41:

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

input:

4
2
3
2
5

output:

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

input:

4
2
3
5

output:

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

result:

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

Test #43:

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

input:

4
2
5
2
3

output:

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

input:

4
3
2
5
3

output:

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

result:

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

Test #45:

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

input:

4
5
2
2
3

output:

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

input:

4
5
2
2
3
3

output:

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

input:

4
2
3
2
5

output:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #49:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #50:

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

input:

4
2
3
3
5

output:

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

result:

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

Test #51:

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

input:

4
2
3
2
5

output:

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

input:

4
3
2
5
3

output:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #54:

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

input:

4
3
2
2
3
5

output:

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

input:

4
2
3
2
3
5

output:

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

input:

4
3
2
5
3

output:

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

input:

4
5
2
2
3

output:

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

input:

1000
848
538
219
152
504
438
428
153
719
229
251
597
304
329
138
80
2
36
644
769
207
246
117
205
590
139
189
277
889
122
565
67
147
364
158
465
148
236
85
254
168
400
774
380
280
115
93
392
856
159
716
110
50
42
525
141
232
419
113
771
26
58
8
196
37
84
7
243
344
60
398
40
262
29
778
268
526
546
195...

output:

? 848 946
? 922 538
? 219 259
? 827 152
? 637 504
? 700 438
? 428 432
? 153 762
? 939 719
? 229 945
? 524 251
? 597 666
? 589 304
? 679 329
? 138 274
? 281 80
? 161 2
? 658 36
? 814 644
? 951 769
? 207 322
? 246 675
? 738 117
? 205 929
? 843 590
? 139 982
? 854 189
? 351 277
? 889 977
? 122 870
? 56...

result:

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

Test #59:

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

input:

1000
570
298
528
462
36
745
8
94
184
4
138
265
488
484
228
807
218
551
128
150
227
52
280
521
29
765
335
852
366
394
288
386
443
652
671
747
67
153
58
314
236
34
649
181
148
244
104
930
247
594
101
185
261
376
237
146
68
310
108
2
291
65
489
71
39
139
51
72
120
359
661
409
877
498
516
726
75
40
199
...

output:

? 398 431
? 703 61
? 397 473
? 383 539
? 109 965
? 256 112
? 993 270
? 372 907
? 771 817
? 887 997
? 99 863
? 362 736
? 284 513
? 327 517
? 315 773
? 194 13
? 783 152
? 385 450
? 844 873
? 296 851
? 774 751
? 949 913
? 721 46
? 480 141
? 704 972
? 31 236
? 649 666
? 149 138
? 635 588
? 607 455
? 713...

result:

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

Test #60:

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

input:

1000
427
266
432
54
714
94
10
898
543
9
557
338
749
193
318
732
407
47
222
467
527
325
832
810
85
33
41
227
776
748
586
148
893
311
101
498
3
190
48
57
131
261
579
89
472
112
262
49
385
559
267
188
236
601
83
174
207
540
270
536
86
473
14
142
211
187
324
284
258
374
134
114
240
619
162
61
706
474
16...

output:

? 214 686
? 868 349
? 785 564
? 591 974
? 644 508
? 954 659
? 996 953
? 497 552
? 397 272
? 5 405
? 279 347
? 832 300
? 375 377
? 500 97
? 550 842
? 484 635
? 640 204
? 24 563
? 890 449
? 234 419
? 264 673
? 163 722
? 448 585
? 596 463
? 43 949
? 17 442
? 123 21
? 114 625
? 613 496
? 429 627
? 708 4...

result:

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

Test #61:

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

input:

1000
406
592
588
435
332
824
304
188
336
694
743
385
599
133
755
357
122
792
664
7
563
860
45
440
470
278
56
241
315
6
781
114
732
132
350
72
26
326
500
447
131
23
109
505
291
356
179
143
259
634
377
177
484
29
437
622
30
436
25
171
557
8
417
54
104
729
569
160
549
33
12
380
402
142
335
195
271
462
...

output:

? 403 203
? 296 693
? 515 294
? 783 641
? 166 334
? 412 478
? 179 152
? 94 579
? 168 247
? 347 467
? 425 629
? 671 808
? 701 663
? 263 934
? 623 502
? 728 822
? 61 459
? 448 396
? 387 332
? 918 997
? 719 380
? 430 543
? 978 791
? 508 220
? 235 759
? 139 688
? 28 382
? 880 427
? 465 843
? 319 3
? 610...

result:

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

Test #62:

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

input:

1000
282
350
400
256
20
163
195
919
379
469
190
278
745
147
41
522
121
217
444
604
268
333
780
945
238
63
712
508
293
781
251
319
122
638
513
368
51
353
33
95
162
161
593
90
619
398
265
242
229
597
73
917
78
750
308
113
727
250
62
99
79
271
149
165
462
80
380
620
158
424
594
26
32
551
259
602
40
16
...

output:

? 721 360
? 835 326
? 938 301
? 373 97
? 491 224
? 761 582
? 310 598
? 31 960
? 690 976
? 735 197
? 406 806
? 362 819
? 957 873
? 55 574
? 521 841
? 112 240
? 637 561
? 609 129
? 118 279
? 199 47
? 367 710
? 667 698
? 968 111
? 973 975
? 382 621
? 123 532
? 145 78
? 132 247
? 833 647
? 974 891
? 35 ...

result:

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

Test #63:

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

input:

1000
306
480
305
45
168
605
277
863
112
37
467
810
693
364
409
902
646
96
309
111
793
61
413
14
774
133
831
457
449
284
763
59
452
828
492
263
747
914
92
698
321
76
304
308
156
11
196
106
117
787
174
327
690
459
237
273
200
6
149
713
301
711
688
259
472
397
361
318
244
336
753
715
242
484
354
464
21...

output:

? 953 653
? 37 740
? 348 169
? 851 478
? 584 858
? 198 42
? 362 855
? 974 69
? 94 556
? 482 702
? 11 267
? 905 91
? 154 931
? 682 60
? 802 296
? 952 951
? 823 121
? 76 548
? 776 346
? 445 680
? 907 104
? 470 84
? 756 294
? 507 762
? 887 948
? 434 65
? 85 922
? 31 272
? 276 980
? 876 642
? 119 4
? 47...

result:

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

Test #64:

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

input:

1000
371
198
244
931
183
222
400
38
489
7
653
220
176
233
70
408
66
339
602
28
278
447
622
137
421
211
829
527
539
35
636
112
626
155
541
45
125
410
52
344
620
542
73
40
2
110
21
32
120
101
484
608
203
62
597
811
773
508
6
309
485
330
800
315
260
690
628
216
79
701
830
37
846
268
15
97
87
497
483
10...

output:

? 232 259
? 310 605
? 513 112
? 894 862
? 852 635
? 557 119
? 53 201
? 925 780
? 23 386
? 987 667
? 306 614
? 561 209
? 649 994
? 247 535
? 467 861
? 14 185
? 892 869
? 46 323
? 268 204
? 945 670
? 267 445
? 502 107
? 244 736
? 10 727
? 159 628
? 579 278
? 658 672
? 684 54
? 790 78
? 931 840
? 272 2...

result:

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

Test #65:

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

input:

1000
257
147
306
260
179
96
328
258
263
571
316
329
487
449
762
492
862
575
836
292
651
262
308
371
145
221
43
700
547
232
67
234
364
450
494
797
37
445
620
301
318
70
25
271
136
276
387
909
2
502
44
176
42
650
10
297
416
941
373
457
570
216
164
540
425
291
18
243
218
214
158
21
632
428
72
139
639
5...

output:

? 514 930
? 697 294
? 553 612
? 569 520
? 358 648
? 192 435
? 656 45
? 516 998
? 245 526
? 859 223
? 632 882
? 658 273
? 899 974
? 327 898
? 307 477
? 305 984
? 277 91
? 851 483
? 167 329
? 584 795
? 647 699
? 524 47
? 616 791
? 787 742
? 290 747
? 449 442
? 86 480
? 175 601
? 907 639
? 464 858
? 13...

result:

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

Test #66:

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

input:

1000
629
498
304
738
405
315
451
832
300
127
507
429
414
59
255
165
28
237
138
448
508
91
555
32
183
35
111
606
506
593
549
424
683
285
378
706
260
600
86
234
50
182
249
19
604
471
2
655
703
67
525
208
11
292
81
37
440
43
26
346
481
103
145
541
894
140
515
199
495
85
34
101
61
245
306
90
18
190
618
...

output:

? 628 649
? 820 499
? 305 871
? 896 739
? 404 516
? 314 574
? 450 774
? 833 942
? 301 422
? 126 797
? 506 893
? 428 678
? 918 415
? 639 58
? 254 822
? 804 164
? 565 29
? 236 741
? 634 139
? 479 449
? 841 509
? 90 262
? 554 692
? 391 33
? 182 503
? 180 34
? 110 190
? 900 607
? 786 507
? 592 799
? 548...

result:

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

Test #67:

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

input:

1000
494
474
355
565
210
258
275
458
771
161
306
98
269
147
136
171
286
218
598
756
216
517
690
610
385
206
7
420
139
339
81
202
133
77
158
513
80
45
109
55
572
262
121
191
226
22
11
102
414
528
166
451
188
271
535
561
303
142
179
320
730
32
559
250
760
332
284
225
10
41
93
2
542
453
410
300
575
184...

output:

? 53 506
? 313 526
? 647 546
? 356 437
? 790 304
? 742 734
? 727 179
? 41 542
? 209 231
? 841 638
? 694 530
? 902 741
? 733 334
? 285 855
? 352 864
? 62 831
? 714 671
? 278 782
? 19 402
? 244 22
? 784 369
? 485 159
? 310 296
? 390 257
? 617 554
? 780 794
? 181 995
? 522 580
? 452 863
? 74 663
? 287 ...

result:

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

Test #68:

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

input:

300
139
3
190
31
157
62
188
52
32
156
254
15
268
57
82
121
23
240
161
193
98
25
18
111
70
76
53
183
138
34
197
104
68
14
67
21
89
42
30
38
44
126
63
35
115
20
108
43
5
50
167
101
177
122
107
22
4
16
58
7
77
288
8
51
255
226
41
91
85
119
78
48
204
135
6
245
105
65
200
239
224
28
40
87
39
199
12
103
1...

output:

? 139 281
? 169 3
? 190 230
? 153 31
? 175 157
? 100 62
? 244 188
? 147 52
? 32 207
? 236 156
? 262 254
? 116 15
? 297 268
? 151 57
? 82 219
? 121 256
? 23 26
? 240 299
? 279 161
? 193 229
? 203 98
? 60 25
? 18 217
? 111 273
? 70 114
? 296 76
? 53 86
? 183 247
? 138 196
? 34 276
? 248 197
? 258 104
...

result:

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

Test #69:

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

input:

300
88
161
132
31
41
20
255
154
4
48
202
160
1
86
120
83
23
158
70
54
6
205
102
122
228
192
30
187
68
153
44
43
113
118
274
111
98
157
29
33
12
45
57
189
25
95
135
2
89
104
103
128
292
126
11
93
130
92
283
40
59
117
97
263
63
24
28
123
8
134
262
51
58
146
195
119
65
22
34
50
17
19
3
61
140
5
213
125...

output:

? 120 128
? 268 91
? 215 194
? 255 248
? 83 134
? 233 235
? 262 291
? 254 161
? 86 2
? 58 198
? 182 237
? 223 263
? 253 228
? 225 296
? 151 197
? 1 277
? 98 160
? 137 267
? 10 251
? 18 55
? 84 45
? 241 181
? 162 59
? 132 138
? 75 209
? 269 13
? 143 110
? 240 77
? 219 108
? 180 107
? 252 105
? 81 186...

result:

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

Test #70:

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

input:

1000
872
211
425
809
407
9
268
582
219
315
163
114
868
548
151
906
791
447
703
510
462
606
65
535
474
393
499
411
308
349
201
329
656
517
314
128
256
95
490
244
958
76
139
60
400
618
124
369
580
501
293
164
176
550
230
374
454
390
622
493
1
316
813
370
261
149
644
129
488
359
158
145
615
538
607
508...

output:

? 89 878
? 725 1000
? 567 987
? 380 498
? 545 709
? 946 826
? 468 20
? 25 824
? 292 296
? 309 276
? 248 940
? 533 859
? 417 665
? 522 734
? 107 351
? 434 985
? 523 947
? 608 12
? 422 463
? 781 975
? 471 420
? 928 886
? 806 922
? 221 234
? 370 668
? 729 265
? 227 79
? 835 732
? 599 427
? 713 348
? 64...

result:

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

Test #71:

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

input:

1000
939
489
56
754
378
1215
22
314
241
218
247
351
204
180
851
826
922
29
33
293
608
240
420
586
583
118
536
334
246
239
686
341
338
20
1205
436
226
527
459
181
1102
841
508
541
1716
448
912
370
839
854
1085
482
856
948
789
337
23
39
126
735
933
367
549
635
590
1117
704
1426
371
1592
861
997
1114
1...

output:

? 482 757
? 256 935
? 35 209
? 388 682
? 198 539
? 747 620
? 15 109
? 395 162
? 128 340
? 115 600
? 880 131
? 562 183
? 104 741
? 713 95
? 436 475
? 716 426
? 477 779
? 990 21
? 495 24
? 494 153
? 644 318
? 390 127
? 763 219
? 304 722
? 302 567
? 913 68
? 920 284
? 173 744
? 663 130
? 980 126
? 356 ...

result:

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

Test #72:

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

input:

1000
85538
85890
85414
85423
85476
85623
86013
85589
85404
85906
85484
85770
85980
85709
85725
86382
85843
85930
85428
86132
85686
85512
85434
85591
85586
85882
85751
86041
85876
85653
85679
86055
85855
85874
85676
85600
85994
85817
86320
85643
86163
85464
85400
86383
86011
85461
85595
85420
86076
8...

output:

? 894 139
? 643 491
? 15 480
? 24 128
? 77 435
? 224 922
? 613 635
? 744 190
? 502 5
? 506 598
? 101 85
? 371 931
? 580 846
? 310 971
? 326 898
? 994 982
? 815 444
? 969 530
? 189 29
? 732 781
? 614 287
? 113 498
? 35 74
? 192 298
? 187 341
? 998 483
? 924 352
? 921 641
? 477 695
? 632 254
? 866 280...

result:

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

Test #73:

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

input:

1000
6046
7088
6403
8764
5385
6376
7293
7724
6774
5772
5921
9529
6943
8850
5650
7809
6827
5954
5431
7641
5854
7058
7891
6714
6998
5148
5851
5309
7360
8593
7376
5170
6073
8493
8013
5612
7279
6459
8374
5031
9233
6484
8091
7045
6414
6002
5695
5867
7229
6704
5704
8014
6917
7854
5955
6015
5266
6194
6174
...

output:

? 184 803
? 390 730
? 562 246
? 741 829
? 62 833
? 357 241
? 644 422
? 523 611
? 317 830
? 501 132
? 763 159
? 969 910
? 354 888
? 760 922
? 847 111
? 538 896
? 769 333
? 164 693
? 722 72
? 709 504
? 957 143
? 883 382
? 554 925
? 303 655
? 929 366
? 22 527
? 142 899
? 736 49
? 438 773
? 884 699
? 78...

result:

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

Test #74:

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

input:

1000
4707
4285
4755
4300
4825
4486
4236
4137
5551
4050
4490
4568
5733
4544
4246
4088
4463
4922
4364
5015
4362
4275
5522
4115
4203
4665
4142
5173
4163
4991
4161
4321
4124
4185
4086
5092
4271
4740
4001
4522
4095
4194
5406
4738
4548
4105
5115
4744
4712
5075
4893
4619
4720
4344
4753
4251
4604
5018
4970
...

output:

? 354 774
? 306 153
? 379 811
? 512 161
? 409 938
? 468 247
? 389 126
? 73 87
? 773 827
? 24 29
? 882 250
? 586 280
? 889 870
? 270 940
? 949 133
? 179 42
? 595 237
? 995 459
? 195 297
? 747 506
? 983 194
? 149 840
? 760 755
? 241 58
? 112 753
? 807 329
? 749 78
? 948 592
? 93 523
? 496 789
? 91 196...

result:

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

Test #75:

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

input:

1000
64894
54715
65631
63245
57884
63428
69483
70678
56608
53575
70535
55526
57834
75636
62474
65781
67973
66204
52559
61383
65549
79337
76524
60224
50739
53163
52572
71529
61463
52762
71239
55149
69065
67307
52865
56773
66968
60367
65076
59377
61864
62922
59158
59788
51846
70331
65993
50185
63964
6...

output:

? 396 484
? 277 116
? 418 668
? 605 350
? 263 212
? 356 984
? 735 523
? 656 573
? 627 169
? 91 238
? 570 988
? 133 345
? 791 209
? 724 951
? 327 384
? 785 423
? 491 584
? 438 906
? 320 64
? 730 302
? 414 495
? 807 875
? 994 750
? 893 265
? 16 732
? 82 442
? 65 832
? 597 935
? 303 454
? 297 71
? 650 ...

result:

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

Test #76:

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

input:

1000
47
691
196
606
437
498
816
331
165
270
601
486
526
507
550
490
688
339
562
468
576
415
229
28
403
455
94
93
188
273
76
744
107
135
102
694
226
69
178
416
172
547
337
317
446
111
393
444
462
116
290
101
230
189
136
43
134
56
108
81
245
213
95
9
79
96
109
234
80
57
166
288
714
100
183
716
170
451...

output:

? 604 512
? 297 892
? 51 602
? 884 545
? 707 452
? 740 208
? 71 754
? 955 508
? 338 291
? 367 607
? 812 733
? 49 398
? 518 425
? 697 669
? 198 96
? 47 97
? 52 717
? 822 322
? 210 631
? 728 408
? 659 207
? 55 654
? 730 949
? 332 764
? 651 227
? 578 616
? 364 284
? 254 374
? 152 85
? 699 88
? 716 240
...

result:

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

Test #77:

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

input:

1000
856
1044
866
1024
1080
1171
1070
404
666
997
200
463
1187
40
161
1285
692
855
1206
612
148
637
135
1288
1148
395
108
348
203
893
438
1390
33
195
956
1602
1079
1436
957
241
393
10
16
196
51
735
1421
172
255
1466
716
804
677
711
1263
49
1018
779
92
95
70
477
539
580
397
444
153
317
351
1590
525
8...

output:

? 62 151
? 148 279
? 157 785
? 83 161
? 679 294
? 289 719
? 776 453
? 388 742
? 68 191
? 814 577
? 578 212
? 600 630
? 177 911
? 335 315
? 387 960
? 700 36
? 897 66
? 416 989
? 891 815
? 112 816
? 970 850
? 214 316
? 273 595
? 474 170
? 548 812
? 506 234
? 357 545
? 842 218
? 529 654
? 768 17
? 109 ...

result:

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

Test #78:

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

input:

1000
85489
86057
85786
85922
85745
85422
86121
85757
85853
85454
85405
85501
85881
85830
85808
86086
85823
85506
85778
85439
85616
85537
85787
85716
85726
86218
85442
85588
85712
85498
86114
85668
85617
86065
85456
85408
85964
85559
85941
85446
85790
85911
85894
86238
85969
85687
85629
86070
85544
8...

output:

? 199 992
? 726 12
? 26 200
? 449 772
? 932 392
? 465 54
? 91 182
? 978 95
? 214 590
? 538 360
? 179 390
? 584 435
? 770 949
? 615 853
? 578 875
? 252 281
? 193 550
? 349 479
? 539 548
? 79 930
? 69 710
? 314 796
? 991 597
? 251 704
? 141 428
? 113 218
? 780 739
? 763 789
? 212 537
? 820 627
? 683 7...

result:

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

Test #79:

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

input:

1000
5962
6337
6030
6650
7526
5164
6656
5670
6196
6534
5939
5060
7307
5615
6092
6199
9882
5184
5360
5030
8102
6190
5446
6103
5127
6699
7302
5592
5501
5344
5352
6755
5223
5158
6292
5272
6002
5189
7169
8033
6942
6347
5433
6788
7670
7609
5264
6989
6918
6648
7318
7311
5857
6331
6168
7511
6339
8391
7274
...

output:

? 443 598
? 975 404
? 18 873
? 485 737
? 494 705
? 484 129
? 54 45
? 109 299
? 849 8
? 583 930
? 709 219
? 14 480
? 166 34
? 697 833
? 554 584
? 812 385
? 461 417
? 154 839
? 191 162
? 613 363
? 912 572
? 321 715
? 644 609
? 883 186
? 864 50
? 61 456
? 355 354
? 348 885
? 116 11
? 755 472
? 986 846
...

result:

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

Test #80:

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

input:

1000
4750
4333
5190
4444
4720
4481
4090
5264
4257
4576
4379
4341
4873
5117
4555
4332
4052
5586
4420
4118
5392
4560
4765
4265
4263
4517
5650
4000
5797
4422
4315
4542
4700
5755
4812
4598
4253
4175
5108
4271
4471
4505
4167
4125
4423
5514
4064
5462
4670
5030
4102
4660
4702
4732
4054
4245
4352
5458
4077
...

output:

? 250 807
? 738 750
? 18 720
? 312 93
? 889 371
? 724 874
? 68 770
? 346 901
? 155 841
? 963 790
? 392 333
? 307 846
? 336 620
? 73 831
? 964 808
? 993 267
? 682 142
? 597 837
? 785 956
? 462 369
? 634 718
? 157 234
? 612 721
? 769 684
? 690 420
? 295 563
? 205 198
? 351 551
? 968 719
? 280 793
? 51...

result:

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

Test #81:

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

input:

1000
57068
53752
52619
78843
63359
68806
60440
64082
76197
57444
66962
58419
71087
64757
62150
69701
55246
61766
55555
79174
54065
66100
66225
61317
52965
64631
54256
60585
58703
60832
56319
54300
54005
56337
68896
55634
69828
56666
60966
51443
60291
60959
51289
59891
54947
54208
68621
52978
65901
6...

output:

? 913 994
? 771 734
? 518 131
? 504 322
? 468 145
? 226 337
? 861 524
? 852 761
? 115 170
? 535 603
? 35 810
? 447 558
? 640 983
? 756 843
? 142 346
? 2 185
? 167 88
? 667 100
? 76 317
? 770 153
? 850 122
? 105 781
? 705 533
? 158 412
? 243 865
? 1 818
? 232 650
? 929 752
? 78 368
? 523 838
? 430 6
...

result:

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

Test #82:

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

input:

1000
84
232
228
617
401
442
77
157
404
462
73
321
215
414
567
170
601
129
582
452
326
146
248
877
70
372
19
446
394
249
416
793
158
516
544
283
450
176
469
311
76
881
291
444
402
104
561
72
123
85
713
164
251
225
107
240
25
294
184
5
285
720
619
126
693
440
415
612
481
180
137
433
89
705
292
356
832...

output:

? 336 84
? 948 232
? 614 228
? 617 971
? 967 401
? 903 442
? 77 78
? 236 157
? 862 404
? 574 462
? 218 73
? 461 321
? 972 215
? 483 414
? 852 567
? 543 170
? 601 835
? 638 129
? 849 582
? 554 452
? 326 566
? 834 146
? 328 248
? 952 877
? 252 70
? 447 372
? 829 19
? 446 900
? 914 394
? 776 249
? 416 ...

result:

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

Test #83:

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

input:

1000
22
201
552
446
751
56
70
450
30
37
868
19
514
204
162
734
192
157
294
336
207
550
346
400
663
170
303
707
679
132
542
532
325
343
422
937
813
233
409
418
301
54
483
26
104
526
85
441
572
20
448
148
329
144
350
314
270
239
459
195
898
351
373
121
283
213
602
153
46
47
395
122
69
753
853
141
94
4...

output:

? 154 22
? 671 201
? 727 552
? 953 446
? 921 751
? 56 133
? 70 592
? 450 799
? 30 404
? 519 37
? 868 977
? 19 967
? 516 514
? 204 700
? 251 162
? 734 883
? 192 585
? 440 157
? 294 946
? 336 624
? 316 207
? 550 850
? 346 885
? 667 400
? 663 949
? 983 170
? 303 696
? 801 707
? 851 679
? 132 449
? 986 ...

result:

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

Test #84:

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

input:

1000
754
167
213
61
153
764
577
24
692
111
499
253
11
465
101
67
693
500
102
48
476
318
137
248
71
218
195
715
84
535
443
60
62
328
431
175
750
944
864
222
25
10
56
579
424
28
286
779
481
596
295
269
454
99
361
696
171
73
110
188
12
561
572
121
216
1
393
556
297
903
168
370
331
364
255
409
713
41
71...

output:

? 290 278
? 750 247
? 413 763
? 747 132
? 298 189
? 942 482
? 314 73
? 559 852
? 760 850
? 263 8
? 815 408
? 913 825
? 655 973
? 17 906
? 843 412
? 233 128
? 976 691
? 95 949
? 734 695
? 806 457
? 106 29
? 61 646
? 196 236
? 276 578
? 928 956
? 741 532
? 919 99
? 708 459
? 682 30
? 827 945
? 728 805...

result:

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

Test #85:

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

input:

1000
370
289
715
621
482
342
476
35
682
173
65
155
500
748
427
112
346
116
305
471
186
439
350
501
158
549
10
620
2
592
161
479
190
465
127
327
33
381
113
92
332
306
742
331
37
618
330
333
383
911
366
39
858
697
489
339
374
673
778
84
230
484
560
24
93
211
60
164
505
700
153
550
4
17
757
95
747
274
...

output:

? 370 529
? 289 432
? 932 715
? 734 621
? 482 940
? 524 342
? 476 585
? 35 855
? 741 682
? 485 173
? 696 65
? 155 239
? 831 500
? 801 748
? 427 746
? 112 276
? 346 820
? 116 643
? 623 305
? 708 471
? 186 848
? 703 439
? 979 350
? 557 501
? 608 158
? 622 549
? 386 10
? 853 620
? 982 2
? 592 678
? 971...

result:

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

Test #86:

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

input:

1000
925
102
699
531
95
632
416
82
184
92
595
709
631
473
292
436
85
480
22
178
669
612
701
194
549
274
340
164
461
965
906
323
132
401
47
247
185
207
424
50
349
108
776
386
218
211
146
76
494
116
24
256
818
746
345
276
210
131
354
607
505
90
239
142
31
126
73
133
177
585
157
155
63
646
104
466
588
...

output:

? 954 925
? 359 102
? 699 960
? 531 890
? 179 95
? 888 632
? 416 616
? 700 82
? 947 184
? 92 144
? 595 978
? 709 951
? 631 662
? 473 934
? 548 292
? 838 436
? 85 993
? 480 649
? 756 22
? 252 178
? 669 957
? 679 612
? 722 701
? 194 861
? 549 789
? 274 298
? 992 340
? 164 635
? 558 461
? 1 965
? 937 9...

result:

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

Test #87:

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

input:

1000
336
586
276
941
648
148
695
92
379
836
430
135
265
219
274
552
145
347
5
564
99
94
160
595
592
35
159
172
362
431
222
481
337
46
286
318
292
423
88
206
322
832
385
843
58
61
264
214
652
238
306
256
162
45
373
27
681
250
432
75
146
304
136
588
248
627
646
640
465
447
86
123
118
420
480
195
14
17...

output:

? 758 336
? 776 586
? 276 581
? 941 989
? 648 940
? 241 148
? 768 695
? 92 962
? 982 379
? 866 836
? 430 538
? 217 135
? 307 265
? 219 391
? 628 274
? 783 552
? 145 657
? 769 347
? 5 826
? 564 771
? 99 796
? 94 682
? 221 160
? 979 595
? 600 592
? 35 899
? 159 189
? 172 693
? 526 362
? 431 927
? 222 ...

result:

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

Subtask #3:

score: 31.1754
Acceptable Answer

Test #88:

score: 33.5156
Acceptable Answer
time: 5ms
memory: 12704kb

input:

1500
1294
273
420
532
201
1035
408
691
830
322
945
411
1118
347
789
78
1251
1158
621
142
641
153
547
948
200
321
597
1015
840
914
1152
450
106
658
808
40
53
239
504
284
649
339
141
990
910
1018
859
496
320
516
900
780
593
688
842
693
44
756
1038
261
91
510
491
413
602
66
271
786
338
221
289
807
226
...

output:

? 1294 1425
? 273 1291
? 961 420
? 532 715
? 1381 201
? 1192 1035
? 1154 408
? 691 749
? 1359 830
? 322 456
? 1224 945
? 717 411
? 1118 1225
? 479 347
? 1352 789
? 78 612
? 1319 1251
? 1412 1158
? 621 655
? 1273 142
? 1432 641
? 178 153
? 1495 547
? 1410 948
? 1163 200
? 321 1029
? 1376 597
? 1191 1...

result:

points 0.41894445270 points  0.41894445270 n = 1500, you used 2661 queries

Test #89:

score: 35.1994
Acceptable Answer
time: 15ms
memory: 12936kb

input:

1500
248
320
232
198
1141
239
170
224
1271
1002
450
653
123
22
647
471
517
431
409
74
173
695
236
179
19
377
13
846
1030
480
284
21
832
72
562
364
340
631
453
282
305
957
361
26
321
1
345
547
269
550
1157
157
132
567
84
1090
274
250
362
204
885
830
1043
557
90
283
645
228
375
148
719
319
346
487
289...

output:

? 1253 195
? 425 1181
? 1269 1175
? 1303 451
? 360 335
? 1262 92
? 740 1331
? 168 1277
? 230 218
? 499 476
? 1051 34
? 677 848
? 1378 39
? 1479 1183
? 854 691
? 1030 353
? 318 984
? 90 1070
? 1092 837
? 1427 594
? 1328 240
? 806 785
? 1265 206
? 323 1322
? 1482 211
? 1124 445
? 1488 402
? 454 655
? ...

result:

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

Test #90:

score: 35.8218
Acceptable Answer
time: 4ms
memory: 12656kb

input:

1500
182
464
110
581
210
358
203
175
928
617
862
666
50
938
488
150
319
831
249
63
967
76
215
221
271
170
551
58
11
1008
126
220
312
1260
395
60
137
189
321
398
564
224
36
1041
683
565
1016
228
387
493
223
687
1080
768
624
528
143
1156
43
927
135
61
116
707
499
66
304
797
447
259
888
99
276
544
339
...

output:

? 196 1410
? 621 1269
? 1446 274
? 1166 291
? 1396 949
? 1322 316
? 102 619
? 1316 88
? 1037 806
? 309 697
? 524 1070
? 832 1168
? 374 1476
? 1032 528
? 1257 1169
? 953 1426
? 306 160
? 416 590
? 125 1054
? 32 819
? 484 793
? 1463 1016
? 108 838
? 111 338
? 136 460
? 578 1416
? 771 276
? 1472 696
? ...

result:

points 0.44777283330 points  0.44777283330 n = 1500, you used 2458 queries

Test #91:

score: 34.5851
Acceptable Answer
time: 7ms
memory: 12876kb

input:

1500
255
858
110
349
148
949
322
353
478
510
442
602
722
811
553
539
609
1295
99
7
1113
782
389
79
648
146
718
140
816
947
1016
593
184
103
495
424
903
283
1191
875
275
143
141
168
767
81
677
94
67
174
498
567
750
521
467
312
471
581
241
53
1262
364
1174
766
990
598
810
82
274
1393
636
731
129
138
6...

output:

? 1373 1126
? 429 831
? 55 313
? 1326 1100
? 74 743
? 1026 713
? 1237 161
? 886 1324
? 305 239
? 255 502
? 651 221
? 1140 301
? 361 528
? 1095 1000
? 716 1224
? 1231 888
? 532 1196
? 657 853
? 309 1451
? 1497 147
? 944 868
? 391 738
? 818 1306
? 1191 1461
? 324 496
? 73 861
? 625 359
? 70 963
? 408 ...

result:

points 0.43231361970 points  0.43231361970 n = 1500, you used 2562 queries

Test #92:

score: 31.3899
Acceptable Answer
time: 4ms
memory: 12712kb

input:

1500
1138
251
505
543
1187
770
156
31
549
116
630
913
1050
249
162
69
140
95
1150
273
43
142
1257
865
173
2
187
686
636
25
790
117
565
87
706
53
623
1127
943
689
160
247
1359
309
26
146
332
553
153
98
952
214
215
765
644
137
677
291
563
57
529
100
59
1144
167
366
62
540
82
578
56
410
396
72
718
237
...

output:

? 182 153
? 876 1049
? 1003 1054
? 1022 11
? 116 1344
? 366 294
? 673 259
? 444 766
? 1025 406
? 580 693
? 1211 436
? 17 1207
? 1407 226
? 881 875
? 183 670
? 785 114
? 681 1275
? 798 1349
? 176 128
? 887 5
? 218 772
? 680 998
? 7 1379
? 1183 187
? 837 965
? 750 657
? 844 1135
? 28 408
? 433 1213
? ...

result:

points 0.3923734230 points  0.3923734230 n = 1500, you used 2886 queries

Test #93:

score: 31.1754
Acceptable Answer
time: 6ms
memory: 12656kb

input:

1500
105
79
451
408
544
354
760
63
866
593
781
443
903
301
1203
395
328
445
711
475
531
22
540
31
1130
510
547
983
701
958
294
799
474
168
867
14
43
335
1041
133
90
326
936
384
188
642
1020
930
761
252
793
490
406
852
898
595
906
1223
221
169
548
54
192
275
1051
913
536
76
180
110
1326
236
253
586
2...

output:

? 698 617
? 1472 711
? 310 525
? 972 954
? 1460 1022
? 927 518
? 1130 33
? 719 838
? 1183 1335
? 454 1161
? 1262 360
? 529 1360
? 299 228
? 600 1355
? 90 149
? 1490 553
? 914 1096
? 1129 528
? 395 122
? 1365 513
? 485 15
? 761 1092
? 159 1020
? 735 1133
? 1315 165
? 1005 258
? 152 477
? 1273 259
? 2...

result:

points 0.38969190720 points  0.38969190720 n = 1500, you used 2911 queries

Test #94:

score: 32.2326
Acceptable Answer
time: 6ms
memory: 12880kb

input:

1500
400
294
449
524
604
557
116
1412
61
897
586
49
442
58
560
234
178
811
237
1438
884
434
1088
119
1129
660
175
32
347
16
53
1087
125
161
366
733
694
698
293
15
415
171
1288
950
266
279
304
1180
1173
1344
882
12
756
464
793
1212
490
1010
243
648
752
22
307
703
251
367
808
1056
35
70
867
614
82
138...

output:

? 701 269
? 362 913
? 76 603
? 453 1314
? 498 293
? 387 1100
? 749 1269
? 1324 1372
? 1379 987
? 734 294
? 610 329
? 1403 831
? 617 824
? 1424 1385
? 381 365
? 902 1033
? 1134 1145
? 122 940
? 407 1027
? 1458 1376
? 268 1480
? 633 129
? 676 678
? 930 1263
? 1260 758
? 236 181
? 778 1151
? 1437 1454
...

result:

points 0.40290799730 points  0.40290799730 n = 1500, you used 2792 queries

Test #95:

score: 40.275
Acceptable Answer
time: 4ms
memory: 12932kb

input:

1500
282
1256
1032
159
1085
399
93
762
314
214
44
655
78
1062
46
7
208
1075
894
1254
145
404
198
486
1361
538
226
825
388
67
86
1293
969
587
589
795
266
766
365
492
21
402
253
493
101
177
240
68
1315
142
1308
387
564
537
260
55
503
225
558
390
506
1027
377
731
1021
221
789
328
100
175
511
917
228
11...

output:

? 1078 564
? 413 489
? 235 937
? 758 318
? 225 831
? 798 1217
? 186 661
? 1477 861
? 628 237
? 428 764
? 1344 88
? 1310 1273
? 156 379
? 877 637
? 92 521
? 1206 14
? 958 416
? 851 393
? 1213 131
? 493 207
? 810 290
? 808 1290
? 571 396
? 1256 972
? 279 189
? 1076 373
? 710 452
? 221 1351
? 1146 776
...

result:

points 0.5034369240 points  0.5034369240 n = 1500, you used 2161 queries

Test #96:

score: 32.9306
Acceptable Answer
time: 4ms
memory: 12880kb

input:

1500
1068
907
446
510
218
522
675
663
132
655
257
1108
426
140
955
65
954
463
880
791
461
553
437
1306
531
452
651
44
435
38
767
634
40
820
227
274
861
441
662
345
1094
985
352
195
683
77
158
104
177
470
1400
80
766
524
589
685
582
684
732
1047
422
491
337
63
924
160
207
488
596
240
1001
230
1129
37...

output:

? 1386 1069
? 1122 906
? 447 644
? 511 1377
? 219 711
? 523 870
? 674 1082
? 662 1015
? 628 133
? 959 654
? 1152 256
? 1132 1109
? 427 1076
? 143 141
? 1048 954
? 64 182
? 955 988
? 1317 462
? 881 1173
? 1072 790
? 460 668
? 983 552
? 1043 436
? 1307 1368
? 1194 530
? 453 551
? 650 982
? 45 541
? 14...

result:

points 0.41163208060 points  0.41163208060 n = 1500, you used 2719 queries

Test #97:

score: 39.2657
Acceptable Answer
time: 3ms
memory: 12704kb

input:

1500
329
122
219
978
451
505
259
367
76
104
1346
798
457
346
511
1090
970
1161
473
40
57
944
761
750
1038
64
1165
239
426
139
1019
198
688
21
1012
1206
567
395
354
138
470
634
716
581
356
803
433
525
82
560
404
596
320
50
291
39
877
1132
127
606
712
303
91
605
15
27
1268
249
610
289
376
190
642
1146...

output:

? 214 1173
? 1378 190
? 1283 446
? 522 145
? 726 1051
? 103 997
? 250 1243
? 1135 596
? 680 1424
? 1318 1396
? 154 53
? 445 702
? 769 1045
? 84 1154
? 275 991
? 4 410
? 75 530
? 123 341
? 1029 282
? 1406 1460
? 240 1445
? 556 283
? 343 741
? 312 750
? 462 418
? 346 1436
? 271 337
? 859 1263
? 274 10...

result:

points 0.49082079630 points  0.49082079630 n = 1500, you used 2219 queries

Test #98:

score: 38.1053
Acceptable Answer
time: 9ms
memory: 12896kb

input:

1500
299
86
148
752
46
565
759
504
755
542
900
6
97
380
9
313
535
776
784
628
15
484
244
773
689
396
141
60
262
877
846
637
408
83
152
308
344
99
952
786
70
398
450
253
360
423
374
571
349
668
817
364
630
1202
54
470
358
270
249
13
146
305
654
107
717
946
999
215
227
137
455
250
547
596
1130
276
590...

output:

? 232 1492
? 727 276
? 345 46
? 242 318
? 28 8
? 214 389
? 864 383
? 537 963
? 1165 933
? 1181 6
? 931 346
? 1423 68
? 380 1267
? 1092 20
? 191 650
? 1368 347
? 387 4
? 455 608
? 1250 738
? 351 1231
? 239 653
? 654 553
? 685 757
? 895 1153
? 788 760
? 1198 281
? 1188 569
? 151 1377
? 868 667
? 1491 ...

result:

points 0.47631579120 points  0.47631579120 n = 1500, you used 2292 queries

Test #99:

score: 37.7912
Acceptable Answer
time: 0ms
memory: 12624kb

input:

1500
618
1309
211
806
631
30
669
1217
235
482
25
359
82
57
157
277
176
19
624
171
1423
274
914
220
495
986
203
1143
243
698
641
92
1031
122
181
1043
255
870
1001
935
1273
818
393
636
653
520
594
210
525
236
312
596
101
801
172
1262
555
183
464
85
313
55
196
32
54
200
810
579
95
227
140
757
732
751
1...

output:

? 1051 163
? 594 1190
? 800 244
? 716 943
? 825 654
? 570 1041
? 1339 643
? 461 1324
? 407 1136
? 584 617
? 113 1310
? 1497 796
? 759 460
? 897 209
? 1059 603
? 1016 709
? 55 410
? 162 463
? 232 435
? 1054 373
? 433 609
? 177 1170
? 848 254
? 496 986
? 854 246
? 70 657
? 319 751
? 1285 342
? 595 264...

result:

points 0.47239033360 points  0.47239033360 n = 1500, you used 2313 queries

Test #100:

score: 35.2113
Acceptable Answer
time: 3ms
memory: 12640kb

input:

1500
859
939
201
610
233
50
169
646
506
974
551
80
365
291
95
32
662
144
477
791
305
768
261
219
704
822
164
815
218
115
785
199
651
606
947
548
783
358
490
627
1376
992
584
190
762
155
15
556
108
320
1160
152
418
1167
8
525
594
289
1039
403
107
126
286
40
1316
786
687
763
340
392
863
21
1304
491
93...

output:

? 10 910
? 1361 516
? 874 1181
? 1141 393
? 1132 442
? 554 265
? 1405 625
? 1298 103
? 459 1109
? 1445 305
? 94 672
? 879 376
? 338 1008
? 175 495
? 1105 675
? 1480 1140
? 657 379
? 90 388
? 1146 1493
? 1320 855
? 26 351
? 1464 1160
? 956 152
? 420 1040
? 1318 861
? 881 1382
? 435 307
? 1208 1347
? ...

result:

points 0.44014148270 points  0.44014148270 n = 1500, you used 2508 queries

Test #101:

score: 33.6194
Acceptable Answer
time: 10ms
memory: 12652kb

input:

1500
134
1450
2764
1131
2002
181
1378
1259
1494
415
361
2050
1257
836
950
1930
1793
394
703
1141
588
1009
561
1091
539
283
164
615
2160
1859
236
2282
602
978
1666
1492
15
133
502
1952
1691
253
377
2538
596
1507
1318
1228
1352
1549
150
2336
1895
1462
1718
1650
1464
259
26
159
1710
981
1050
288
700
25...

output:

? 62 808
? 727 1003
? 1388 1483
? 566 878
? 999 1018
? 913 91
? 688 739
? 866 629
? 1002 752
? 1075 200
? 178 1112
? 1338 1020
? 628 835
? 411 781
? 464 604
? 1398 964
? 902 1303
? 189 1069
? 349 894
? 1024 570
? 369 290
? 845 502
? 278 615
? 635 544
? 1219 267
? 1373 142
? 1101 83
? 302 435
? 1209 ...

result:

points 0.42024203870 points  0.42024203870 n = 1500, you used 2651 queries

Test #102:

score: 33.5362
Acceptable Answer
time: 9ms
memory: 12652kb

input:

1500
85235
85177
85313
86144
85117
85962
86125
86318
86034
86026
85509
85861
85761
85792
86057
85549
85516
85744
85073
85838
85477
84916
85042
84981
85136
86059
85586
85287
85605
85618
85681
85446
85337
85174
85747
86001
85039
85121
86350
84954
85226
85473
85241
85196
85218
84947
85160
85238
84914
8...

output:

? 1172 336
? 278 325
? 413 1484
? 1427 1244
? 218 889
? 1062 1212
? 1225 1470
? 1422 1418
? 1134 1361
? 1152 1126
? 609 677
? 961 1488
? 861 1037
? 1396 892
? 1347 1157
? 649 1038
? 616 981
? 844 1306
? 174 1435
? 938 1280
? 1068 577
? 127 17
? 143 348
? 763 82
? 1041 237
? 1297 1159
? 686 986
? 131...

result:

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

Test #103:

score: 33.5881
Acceptable Answer
time: 2ms
memory: 12948kb

input:

1500
7814
5697
5156
7982
7012
8894
5581
5164
6240
5033
5251
5939
5631
9634
6331
7333
9272
7710
5515
5945
8133
6361
5215
5467
8317
6454
6307
5816
6311
6131
7825
8840
5977
8767
5505
6109
5637
7458
6039
5790
7063
9268
5288
8079
7069
7210
6648
5787
6300
6752
5350
9044
5136
7635
5913
7125
5147
5166
5315
...

output:

? 896 865
? 209 866
? 44 1301
? 919 995
? 672 626
? 1328 1186
? 182 348
? 46 482
? 381 415
? 1176 13
? 85 147
? 283 1211
? 195 1215
? 1393 1444
? 412 558
? 725 1268
? 1368 1290
? 937 832
? 162 337
? 1153 285
? 1193 965
? 742 424
? 69 1390
? 417 149
? 1022 1285
? 454 511
? 402 1106
? 469 246
? 404 13...

result:

points 0.41985158290 points  0.41985158290 n = 1500, you used 2654 queries

Test #104:

score: 33.7662
Acceptable Answer
time: 3ms
memory: 12712kb

input:

1500
4189
5099
4216
4641
5079
5000
4113
4881
5097
4587
4862
4138
4026
4072
5108
5195
4268
5338
4060
4427
5083
4114
4886
5393
4050
4770
4903
4473
4689
5033
4079
5075
4145
5248
5483
5036
5060
5085
4727
4495
4200
4999
4032
4443
4059
5410
5892
4941
5488
4715
4527
4670
4328
4335
4097
4778
4383
5604
5004
...

output:

? 148 400
? 1367 827
? 812 171
? 484 1459
? 810 907
? 750 1197
? 89 1082
? 1366 655
? 1172 825
? 442 539
? 641 951
? 108 1429
? 21 1323
? 313 58
? 1124 834
? 903 979
? 211 386
? 1296 1004
? 49 519
? 437 327
? 1170 814
? 90 699
? 729 658
? 1138 1041
? 1152 41
? 583 704
? 1422 672
? 361 472
? 522 868
...

result:

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

Test #105:

score: 33.6089
Acceptable Answer
time: 14ms
memory: 12948kb

input:

1500
60602
52673
55060
56481
51943
67663
51441
52950
66231
69800
70463
50895
71615
71799
61814
50047
76917
54138
60014
52375
52230
52871
70637
69107
53863
50266
74356
57693
72466
51751
78236
55526
53122
54157
56585
56112
79729
57183
59476
66982
71200
70478
57593
60768
57665
66965
79401
75157
70293
5...

output:

? 1160 465
? 128 1469
? 236 1114
? 1165 301
? 1371 99
? 758 1096
? 449 80
? 614 143
? 1336 700
? 987 848
? 877 1392
? 56 595
? 1487 930
? 942 1420
? 510 1053
? 2 591
? 1258 1143
? 279 197
? 440 704
? 116 1158
? 107 404
? 137 656
? 890 1283
? 997 821
? 811 182
? 589 15
? 1102 1033
? 1454 345
? 1378 9...

result:

points 0.42011177380 points  0.42011177380 n = 1500, you used 2652 queries

Test #106:

score: 36.3729
Acceptable Answer
time: 13ms
memory: 12772kb

input:

1500
108
340
389
297
632
803
586
544
57
160
515
1352
322
1135
728
808
970
352
199
467
909
338
445
1096
27
651
298
125
1205
484
1010
255
423
862
111
1038
992
171
991
316
758
44
331
598
212
792
714
209
1058
195
104
1047
612
568
341
162
32
697
82
1026
337
1268
884
123
913
46
364
453
373
293
323
83
461
...

output:

? 1341 47
? 664 509
? 985 349
? 915 1133
? 475 193
? 1085 1339
? 493 1176
? 562 1138
? 1370 740
? 260 157
? 578 325
? 954 994
? 796 760
? 348 1098
? 1343 484
? 162 160
? 1147 956
? 98 1094
? 369 429
? 873 405
? 529 860
? 1038 596
? 531 870
? 203 973
? 306 1020
? 1178 1030
? 1103 1433
? 1467 1285
? 3...

result:

points 0.45466139020 points  0.45466139020 n = 1500, you used 2415 queries

Test #107:

score: 36.7188
Acceptable Answer
time: 5ms
memory: 12868kb

input:

1500
1648
1217
92
403
214
311
685
1615
856
89
555
144
348
1126
167
1308
248
1764
818
1846
652
1167
1333
476
271
865
401
351
1601
185
845
925
928
1169
373
1516
1195
952
24
1435
170
357
435
1150
1069
241
469
1614
591
785
380
1473
433
862
733
1382
332
809
247
613
179
763
230
83
1693
973
1445
478
259
36...

output:

? 855 43
? 250 663
? 309 7
? 322 828
? 287 402
? 463 661
? 82 991
? 417 656
? 345 1299
? 220 950
? 141 1124
? 276 1481
? 1467 1041
? 1085 962
? 1232 768
? 399 1032
? 617 697
? 376 754
? 728 1421
? 226 1431
? 1472 612
? 254 145
? 510 951
? 211 116
? 852 1191
? 672 931
? 466 721
? 1250 888
? 1264 1030...

result:

points 0.45898541470 points  0.45898541470 n = 1500, you used 2389 queries

Test #108:

score: 36.3729
Acceptable Answer
time: 10ms
memory: 12696kb

input:

1500
85133
85874
85812
85082
85382
85748
85540
85542
85828
86041
84978
85254
85146
85517
85402
85168
84968
84929
85993
85794
84951
85086
85138
85857
85069
85609
85078
85075
85210
85047
86056
85195
85481
85161
85424
85575
85109
85603
85080
85428
84906
85369
85449
85338
85125
85058
85258
85496
85341
8...

output:

? 386 857
? 229 1224
? 343 31
? 418 920
? 1360 1110
? 960 951
? 1021 730
? 496 259
? 1223 1499
? 302 1118
? 1010 1478
? 983 984
? 916 1242
? 947 825
? 380 1047
? 379 838
? 450 1027
? 1452 214
? 907 1035
? 1240 941
? 211 1071
? 1279 784
? 1338 48
? 509 99
? 990 171
? 1273 264
? 290 1299
? 102 442
? 3...

result:

points 0.45466139020 points  0.45466139020 n = 1500, you used 2415 queries

Test #109:

score: 39.6731
Acceptable Answer
time: 14ms
memory: 12644kb

input:

1500
6066
7289
5251
7007
6612
6152
7010
9445
5056
5416
8818
7322
7681
5862
7041
8316
5662
5160
6294
5511
8147
5164
5637
7129
7034
5279
7166
9451
8711
5526
5744
5058
7168
7830
8081
7449
7556
8036
7378
5465
6687
8615
6502
5015
6968
5419
5098
7324
6096
5911
5412
8408
7958
5706
6855
7286
5030
5860
5316
...

output:

? 660 406
? 771 1005
? 78 1341
? 552 1048
? 698 106
? 897 847
? 1163 183
? 238 1123
? 1020 594
? 192 1376
? 862 686
? 916 661
? 798 231
? 740 524
? 1173 774
? 418 109
? 1136 263
? 1451 1244
? 214 998
? 1054 1200
? 1328 917
? 1193 375
? 404 620
? 1275 465
? 1090 829
? 1381 876
? 560 1146
? 674 1140
?...

result:

points 0.49591322320 points  0.49591322320 n = 1500, you used 2195 queries

Test #110:

score: 37.7765
Acceptable Answer
time: 12ms
memory: 12932kb

input:

1500
4218
4690
4101
4323
4706
4900
4534
4632
4382
4393
4488
5374
4495
4288
5538
5354
4861
5425
4444
5202
4857
4493
5141
4412
4011
4910
5169
5008
4063
5698
4688
4105
4187
4289
4566
5390
4224
4262
4959
5325
4730
4932
4591
4529
4563
4940
4318
4787
4639
5252
4157
5750
4592
5529
4351
5309
4369
4202
4114
...

output:

? 1111 921
? 433 1115
? 1149 280
? 384 822
? 1252 1321
? 954 746
? 828 763
? 16 21
? 855 547
? 327 272
? 498 990
? 507 904
? 1044 520
? 1398 720
? 176 1290
? 391 863
? 852 1187
? 510 1209
? 1484 549
? 1057 1478
? 898 72
? 946 54
? 458 248
? 210 791
? 532 1049
? 1437 952
? 1090 445
? 744 127
? 974 56...

result:

points 0.47220594510 points  0.47220594510 n = 1500, you used 2314 queries

Test #111:

score: 38.1813
Acceptable Answer
time: 4ms
memory: 12636kb

input:

1500
59821
52164
51675
72169
64906
54402
55505
62417
50634
64875
79906
59681
60001
55019
61565
81450
58117
65916
53888
59770
50308
54039
55571
76576
52428
55937
56110
63071
60614
62297
65816
67530
51102
79575
53241
62554
52965
59926
63450
55739
51472
66742
73204
51548
76271
56501
52845
64959
65591
5...

output:

? 1087 370
? 853 906
? 609 328
? 1114 1016
? 497 1307
? 1358 734
? 800 499
? 1229 4
? 878 714
? 423 76
? 1351 500
? 226 625
? 424 1205
? 1138 245
? 989 1420
? 1400 1136
? 1121 1192
? 1264 763
? 437 1332
? 477 751
? 356 1391
? 627 770
? 1052 662
? 17 874
? 1120 1377
? 1077 218
? 77 624
? 241 265
? 32...

result:

points 0.47726576270 points  0.47726576270 n = 1500, you used 2287 queries

Test #112:

score: 38.4433
Acceptable Answer
time: 5ms
memory: 12632kb

input:

1500
228
275
399
396
240
22
61
235
460
199
347
949
102
903
390
516
861
1095
1183
1029
827
893
376
231
227
139
963
348
276
672
631
444
867
626
1319
156
677
372
668
470
530
255
906
220
1370
63
685
491
737
558
601
554
1195
967
633
1150
11
242
362
749
550
402
262
113
133
98
170
899
186
146
183
398
403
7...

output:

? 1371 228
? 508 275
? 852 399
? 396 657
? 240 588
? 22 547
? 61 1463
? 235 1318
? 460 635
? 199 1053
? 347 1440
? 1115 949
? 545 102
? 1497 903
? 390 813
? 1103 516
? 1041 861
? 1152 1095
? 1183 1439
? 1029 1240
? 1478 827
? 1051 893
? 879 376
? 511 231
? 227 259
? 139 514
? 1109 963
? 348 1337
? 2...

result:

points 0.48054142280 points  0.48054142280 n = 1500, you used 2270 queries

Test #113:

score: 38.5686
Acceptable Answer
time: 4ms
memory: 12888kb

input:

1500
217
194
244
895
532
572
561
125
1086
271
27
658
246
379
516
529
440
31
383
857
1400
407
1158
81
1120
606
326
428
130
466
798
116
1168
151
6
240
197
526
317
119
223
293
1040
233
63
659
176
627
98
128
1124
749
299
227
557
19
759
337
1118
489
568
172
592
84
249
202
432
43
435
33
527
214
881
350
16...

output:

? 217 1031
? 194 224
? 882 244
? 895 1010
? 907 532
? 594 572
? 561 717
? 125 751
? 1086 1134
? 1070 271
? 27 503
? 658 1401
? 246 1339
? 1389 379
? 516 1139
? 529 750
? 440 1422
? 1390 31
? 1106 383
? 857 1165
? 1431 1400
? 407 1085
? 1376 1158
? 352 81
? 1120 1394
? 1454 606
? 1251 326
? 1075 428
...

result:

points 0.48210801660 points  0.48210801660 n = 1500, you used 2262 queries

Test #114:

score: 34.7329
Acceptable Answer
time: 0ms
memory: 12700kb

input:

1500
248
609
142
130
828
842
226
122
620
888
509
1067
408
257
1104
268
1394
480
745
227
685
482
797
360
73
780
69
256
390
473
938
95
307
1015
1158
670
91
75
410
301
971
324
590
393
687
70
100
168
729
1108
109
394
392
1328
314
208
274
641
297
664
391
466
813
713
852
255
1103
574
29
265
1282
1254
677
...

output:

? 1043 469
? 409 765
? 1375 962
? 639 947
? 1233 1262
? 1347 1422
? 113 912
? 547 282
? 625 369
? 275 35
? 1092 926
? 913 531
? 8 285
? 1399 1231
? 1224 442
? 927 121
? 81 778
? 952 1058
? 358 770
? 468 619
? 665 904
? 1292 209
? 438 558
? 991 9
? 91 634
? 692 1148
? 948 1409
? 44 1428
? 1381 552
? ...

result:

points 0.43416110870 points  0.43416110870 n = 1500, you used 2549 queries

Test #115:

score: 33.6611
Acceptable Answer
time: 10ms
memory: 12772kb

input:

1500
682
718
767
623
275
571
659
67
958
295
954
507
95
35
1101
381
199
746
323
617
426
521
1027
140
226
312
615
526
14
991
772
1122
798
227
892
353
855
236
752
205
599
247
699
503
453
787
524
546
513
147
720
133
260
130
253
448
973
101
859
209
433
239
591
901
432
12
1153
37
871
641
691
1034
697
705
...

output:

? 682 1246
? 718 1050
? 767 1249
? 902 623
? 1363 275
? 1285 571
? 1440 659
? 67 1157
? 1128 958
? 1049 295
? 954 1023
? 507 863
? 370 95
? 612 35
? 1426 1101
? 381 952
? 199 1104
? 943 746
? 1409 323
? 617 624
? 810 426
? 1229 521
? 1027 1276
? 1060 140
? 226 532
? 312 1441
? 615 648
? 560 526
? 14...

result:

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

Test #116:

score: 33.5156
Acceptable Answer
time: 14ms
memory: 12636kb

input:

1500
310
1215
1231
797
335
238
389
549
655
1451
716
122
382
841
733
345
78
483
203
671
100
1275
755
434
600
801
59
935
1077
173
386
379
554
451
7
595
286
96
1091
992
106
374
1224
303
548
90
986
576
759
471
57
131
966
1198
578
18
416
6
452
556
376
891
632
387
185
897
1131
104
380
822
1150
265
368
898...

output:

? 1229 310
? 1297 1215
? 1362 1231
? 925 797
? 335 1246
? 238 726
? 1481 389
? 952 549
? 655 668
? 1464 1451
? 1052 716
? 256 122
? 382 1409
? 1377 841
? 733 1477
? 603 345
? 577 78
? 843 483
? 234 203
? 671 1140
? 209 100
? 1275 1476
? 755 1465
? 1020 434
? 600 707
? 801 1408
? 139 59
? 935 1395
? ...

result:

points 0.41894445270 points  0.41894445270 n = 1500, you used 2661 queries

Test #117:

score: 33.464
Acceptable Answer
time: 15ms
memory: 12940kb

input:

1500
596
463
74
112
502
104
270
896
487
255
451
174
508
166
590
833
1219
147
341
1312
84
25
334
233
382
10
965
519
192
434
57
558
317
979
281
734
358
1006
589
684
1220
313
180
363
1374
1003
588
797
730
388
54
386
418
607
847
528
747
181
168
496
1172
114
160
453
228
483
1248
35
676
1157
520
1141
263
...

output:

? 1437 596
? 497 463
? 882 74
? 112 1061
? 1170 502
? 1258 104
? 560 270
? 896 1380
? 663 487
? 255 600
? 451 1125
? 174 690
? 771 508
? 784 166
? 977 590
? 1391 833
? 1488 1219
? 952 147
? 725 341
? 1331 1312
? 1279 84
? 25 1153
? 334 858
? 603 233
? 382 612
? 10 122
? 1028 965
? 519 583
? 192 1097...

result:

points 0.4182998450 points  0.4182998450 n = 1500, you used 2666 queries