QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765722#8267. Staring Contest_8_8_#53.840325 22ms12944kbC++204.4kb2024-11-20 15:05:272024-11-20 15:05:28

Judging History

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

  • [2024-11-20 15:05:28]
  • 评测
  • 测评结果:53.840325
  • 用时:22ms
  • 内存:12944kb
  • [2024-11-20 15:05:27]
  • 提交

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(val > max(nv[0], bf[0])) {
                res[nv[2]] = nv[0];
                res[bf[2]] = bf[0];
                if(f.size() > 1) {
                    bf = f.back();
                    f.pop_back();
                    continue;
                }
            }
            if(nv[0] < bf[0]) res[nv[2]] = nv[0];
            else{
                res[bf[2]] = bf[0];
                bf = nv;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!res[i]) {
            nx.push_back(i);
        }
    }
    // assert((int)nx.size() <= (int)x.size() / 2 + 2);
    solve(nx);
}
bool check() {
    int c = 0;
    for(int i = 1; i <= n; i++) {
        if(res[i] > a[i]) return false;
        if(res[i] < a[i]) c++;
    }
    return (c <= 1);
}
bool str = 0;
void test() {
    memset(mem, -1, sizeof(mem));
    for(int i = 1; i <= n; i++) {
        res[i] = 0;
    }
    if(!str) {
        cin >> n;
        if(loc) {
            for(int i = 1; i <= n; i++) {
                cin >> a[i];
            }
        }
    }
    vector<int> f(n);
    iota(f.begin(), f.end(), 1);
    shuffle(f.begin(), f.end(), rng);
    solve(f);
    int mx = 0;
    for(int i = 1; i <= n; i++) {
        mx = max(mx ,res[i]);
    }
    for(int i =1; i <= n; i++) {
        if(!res[i]) res[i] = mx;
    }
    if(!str) {
        cout << "! ";
        for(int i = 1; i <= n; i++) {
            cout << res[i] << ' ';
        }
    }
}

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

    while(t--) 
        test();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9
Accepted

Test #1:

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

input:

2
1

output:

? 2 1
! 1 1 

result:

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

Test #2:

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

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

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #4:

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

input:

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

output:

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

result:

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

Test #5:

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

input:

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

output:

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

result:

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

Test #6:

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

input:

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

output:

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

result:

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

Test #7:

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

input:

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

output:

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

result:

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

Test #8:

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

input:

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

output:

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

result:

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

Test #9:

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

input:

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

output:

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

result:

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

Test #10:

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

input:

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

output:

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

result:

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

Test #11:

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

input:

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

output:

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

result:

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

Test #12:

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

input:

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

output:

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

result:

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

Test #13:

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

input:

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

output:

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

result:

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

Test #14:

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

input:

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

output:

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

result:

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

Test #15:

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

input:

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

output:

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

result:

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

Test #16:

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

input:

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

output:

? 1 9
? 4 7
? 6 10
? 5 8
? 3 2
? 5 3
? 6 3
? 4 6
? 1 6
? 9 8
? 7 2
? 9 7
? 6 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: 0ms
memory: 12508kb

input:

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

output:

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

result:

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

Test #18:

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

input:

50
86362
86376
86357
86363
86354
86351
86373
86358
86381
86382
86377
86370
86368
86369
86355
86367
86386
86366
86364
86361
86392
86390
86350
86353
86356
86353
86356
86385
86390
86361
86374
86366
86392
86367
86355
86369
86368
86378
86388
86382
86358
86383
86351
86375
86376
86393
86398
86395
86389
863...

output:

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

result:

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

Test #19:

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

input:

50
5703
5454
6099
7174
5914
5076
8947
5302
6767
6109
7563
6651
5813
5773
8526
6824
8198
6375
7026
6476
7060
7159
8878
8428
8143
8143
8428
7159
7060
6476
7993
6375
8878
7779
8526
5773
6297
6651
9491
8883
5302
5076
7663
8060
6099
5454
5703
9654
9491
9258
8947
8917
8098
8006
7779
7233
5406
6926
7560
79...

output:

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

result:

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

Test #20:

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

input:

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

output:

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

result:

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

Test #21:

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

input:

50
78936
54962
66780
56134
58109
52604
70891
69824
68459
62431
57154
67305
66090
53250
52428
58019
52391
51290
54556
65062
50293
50918
67638
72805
56501
76687
78428
50293
54556
68114
61154
56991
66090
57154
73877
82385
52604
70252
67289
70891
54962
75306
80336
75306
74688
67289
57364
59551
70252
751...

output:

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

result:

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

Test #22:

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

input:

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

output:

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

result:

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

Test #23:

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

input:

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

output:

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

result:

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

Test #24:

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

input:

50
86371
86357
86360
86351
86352
86370
86364
86361
86355
86359
86372
86380
86353
86391
86363
86374
86350
86375
86362
86368
86377
86356
86358
86392
86381
86390
86392
86356
86398
86378
86350
86374
86369
86389
86353
86385
86383
86391
86384
86361
86370
86382
86351
86357
86371
86367
86354
86373
86385
863...

output:

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

result:

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

Test #25:

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

input:

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

output:

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

result:

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

Test #26:

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

input:

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

output:

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

result:

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

Test #27:

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

input:

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

output:

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

result:

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

Test #28:

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

input:

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

output:

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

result:

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

Test #29:

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

input:

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

output:

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

result:

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

Test #30:

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

input:

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

output:

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

result:

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

Test #31:

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

input:

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

output:

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

result:

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

Test #32:

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

input:

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

output:

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

result:

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

Test #33:

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

input:

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

output:

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

result:

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

Test #34:

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

input:

4
3
2
3
2
5

output:

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

result:

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

Test #35:

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

input:

4
5
2
2
3

output:

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

result:

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

Test #36:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #37:

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

input:

4
3
2
2
5
3

output:

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

input:

4
3
2
5

output:

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

result:

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

Test #39:

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

input:

4
5
2
2
3

output:

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

input:

4
5
2
3
3

output:

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

input:

4
3
2
2
3
5

output:

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

input:

4
3
2
5

output:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #44:

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

input:

4
3
2
5

output:

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

result:

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

Test #45:

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

input:

4
2
3
2
3
5

output:

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

result:

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

Test #46:

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

input:

4
3
2
5

output:

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

result:

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

Test #47:

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

input:

4
3
2
5

output:

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

result:

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

Test #48:

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

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

input:

4
3
2
5

output:

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

result:

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

Test #50:

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

input:

4
3
2
3
5
2

output:

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

result:

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

Test #51:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #52:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #53:

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

input:

4
3
2
3
2
5

output:

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

result:

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

Test #54:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #55:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #56:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #57:

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

input:

4
2
3
2
5

output:

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

input:

1000
569
9
330
563
327
597
80
192
295
229
142
102
742
462
848
122
99
333
52
491
277
596
117
593
312
395
526
16
221
776
322
262
53
670
194
235
464
29
174
571
637
6
682
282
393
265
564
133
486
683
153
463
507
772
72
267
7
454
313
536
474
500
567
602
219
614
4
823
249
710
239
533
158
178
607
649
128
10...

output:

? 738 569
? 9 577
? 952 330
? 880 563
? 327 976
? 953 597
? 80 560
? 192 793
? 295 510
? 761 229
? 264 142
? 102 833
? 742 899
? 462 573
? 974 848
? 636 122
? 99 449
? 333 599
? 522 52
? 491 753
? 820 277
? 969 596
? 117 645
? 763 593
? 312 540
? 439 395
? 898 526
? 336 16
? 221 301
? 776 910
? 322 ...

result:

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

Test #59:

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

input:

1000
67
198
420
47
56
224
203
258
74
451
431
340
186
206
300
204
171
610
745
685
583
540
388
120
674
363
669
94
221
645
542
533
9
220
334
494
837
632
75
651
617
156
459
101
44
33
83
228
397
653
614
32
808
471
447
373
377
80
815
387
147
584
775
608
733
744
253
50
619
92
64
181
93
273
380
104
217
539
...

output:

? 934 871
? 157 803
? 581 12
? 954 91
? 945 467
? 777 24
? 798 123
? 477 743
? 1 927
? 11 550
? 366 570
? 661 25
? 281 815
? 779 795
? 464 701
? 797 265
? 830 514
? 264 391
? 81 256
? 316 28
? 18 418
? 461 171
? 471 613
? 772 881
? 246 327
? 638 372
? 50 332
? 907 176
? 288 780
? 345 356
? 412 459
?...

result:

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

Test #60:

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

input:

1000
317
300
344
559
213
188
59
151
844
61
112
359
205
601
657
15
161
381
67
751
162
6
54
551
215
163
206
142
439
506
138
152
700
208
948
97
200
145
599
75
1
41
65
93
533
500
47
258
155
113
277
862
198
349
22
470
526
141
364
147
176
230
55
635
755
544
252
270
263
127
519
342
371
43
108
193
139
31
52...

output:

? 494 159
? 468 851
? 829 713
? 509 280
? 235 107
? 907 529
? 742 30
? 117 76
? 500 579
? 463 31
? 598 945
? 180 444
? 247 103
? 539 301
? 377 329
? 8 617
? 81 689
? 238 191
? 381 34
? 376 573
? 776 920
? 998 402
? 974 339
? 334 276
? 622 108
? 136 82
? 898 890
? 726 930
? 369 220
? 748 488
? 123 93...

result:

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

Test #61:

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

input:

1000
867
265
106
87
407
30
544
81
33
335
156
351
348
148
84
183
393
890
203
701
284
621
468
170
86
337
23
584
565
252
574
433
162
200
798
668
310
345
221
382
350
541
855
363
17
517
111
22
208
213
617
663
739
553
92
371
580
677
513
234
54
409
420
374
570
130
128
512
82
10
48
2
288
471
125
540
724
119...

output:

? 560 567
? 868 146
? 311 53
? 905 957
? 797 598
? 15 276
? 272 490
? 73 960
? 984 646
? 833 356
? 835 78
? 317 825
? 237 174
? 259 74
? 533 42
? 909 498
? 804 420
? 445 545
? 731 899
? 650 524
? 589 142
? 690 526
? 234 367
? 454 85
? 300 43
? 820 832
? 989 756
? 292 678
? 718 702
? 183 126
? 287 69...

result:

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

Test #62:

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

input:

1000
238
425
527
545
89
15
97
286
360
167
304
233
520
53
87
334
799
128
239
457
268
399
237
203
391
374
778
278
269
91
200
148
477
287
779
31
160
248
562
673
59
208
64
528
67
756
435
654
175
224
73
127
373
577
118
469
609
632
880
576
158
150
365
506
588
253
225
11
356
68
869
393
106
541
207
679
85
6...

output:

? 961 382
? 713 876
? 764 219
? 773 813
? 545 222
? 508 440
? 273 549
? 753 358
? 321 122
? 887 584
? 349 754
? 617 804
? 241 111
? 527 923
? 544 836
? 334 295
? 900 929
? 437 599
? 336 620
? 729 869
? 367 261
? 914 700
? 175 619
? 204 602
? 696 814
? 314 704
? 112 892
? 362 318
? 639 635
? 370 546
...

result:

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

Test #63:

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

input:

1000
93
614
217
127
286
490
207
532
29
69
22
332
153
427
504
309
195
274
41
333
371
104
446
383
227
288
506
308
180
35
139
200
657
102
223
375
377
325
154
464
265
230
120
199
338
658
363
445
622
237
458
448
411
297
441
58
903
527
65
783
301
572
198
393
188
89
174
271
359
484
253
530
408
353
260
257
...

output:

? 454 291
? 950 807
? 392 89
? 437 870
? 243 643
? 745 193
? 397 94
? 959 766
? 486 700
? 87 466
? 511 131
? 91 666
? 743 424
? 759 287
? 168 752
? 346 926
? 22 403
? 780 637
? 480 616
? 334 302
? 230 315
? 803 552
? 723 215
? 979 309
? 116 387
? 644 972
? 753 830
? 296 654
? 590 849
? 206 483
? 821...

result:

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

Test #64:

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

input:

1000
11
286
122
416
675
325
446
373
846
219
402
14
55
921
903
832
39
218
119
351
62
253
56
44
575
214
153
474
736
712
25
7
357
82
245
318
423
543
140
81
517
60
534
183
763
546
706
523
281
50
28
347
624
952
329
473
316
2
809
154
745
234
57
107
327
597
169
115
178
143
92
364
344
27
230
102
355
452
188...

output:

? 699 979
? 392 429
? 757 549
? 169 159
? 668 350
? 351 249
? 109 714
? 160 255
? 692 922
? 441 563
? 65 197
? 973 637
? 192 891
? 842 900
? 978 806
? 664 964
? 500 923
? 161 565
? 684 763
? 299 594
? 129 877
? 495 15
? 508 889
? 305 913
? 150 228
? 718 573
? 695 678
? 758 53
? 566 472
? 770 424
? 5...

result:

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

Test #65:

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

input:

1000
389
212
108
678
467
102
392
95
53
572
682
116
27
696
382
139
562
814
347
316
31
292
610
30
653
639
294
117
63
130
772
150
618
64
427
218
173
141
613
539
83
713
187
709
498
168
566
22
111
137
508
153
509
9
281
486
407
420
337
71
452
419
803
607
655
4
263
441
124
45
755
178
59
181
300
593
442
559...

output:

? 778 941
? 542 424
? 216 464
? 165 645
? 757 934
? 204 388
? 784 681
? 304 190
? 746 106
? 857 789
? 637 633
? 232 317
? 54 229
? 109 609
? 764 671
? 420 278
? 877 429
? 347 373
? 379 694
? 632 203
? 62 461
? 584 961
? 199 781
? 60 650
? 617 695
? 723 173
? 635 588
? 833 234
? 126 911
? 991 260
? 1...

result:

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

Test #66:

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

input:

1000
385
458
89
80
469
491
35
483
510
12
552
30
145
57
188
84
315
41
140
425
394
250
438
175
356
459
31
599
721
50
451
542
396
615
281
270
199
479
853
804
521
515
118
63
358
142
674
106
95
450
130
38
197
186
70
211
306
191
180
559
890
66
29
462
144
371
79
113
249
943
153
866
456
445
628
402
164
807
...

output:

? 384 862
? 533 459
? 102 88
? 591 81
? 483 468
? 788 490
? 166 34
? 617 482
? 656 511
? 13 854
? 553 667
? 31 974
? 213 144
? 270 56
? 189 731
? 85 680
? 323 314
? 142 40
? 441 141
? 569 424
? 395 570
? 251 810
? 836 439
? 224 174
? 357 588
? 657 458
? 962 30
? 943 598
? 795 720
? 586 51
? 450 840
...

result:

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

Test #67:

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

input:

1000
325
557
260
35
182
212
513
464
566
162
400
309
540
824
47
303
448
221
577
40
889
522
306
204
255
252
282
438
789
580
266
786
179
5
324
208
108
701
143
12
412
502
430
99
718
113
183
531
563
14
293
630
431
251
38
265
196
506
796
268
617
140
213
554
658
215
26
611
541
58
433
195
414
396
419
474
77...

output:

? 677 116
? 445 369
? 740 30
? 692 967
? 329 818
? 788 621
? 489 239
? 536 462
? 434 211
? 403 838
? 600 134
? 542 693
? 460 422
? 176 24
? 955 791
? 699 614
? 107 552
? 781 100
? 425 345
? 960 133
? 113 11
? 161 478
? 694 455
? 325 796
? 473 747
? 682 748
? 188 718
? 232 562
? 213 192
? 420 47
? 73...

result:

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

Test #68:

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

input:

300
36
136
24
8
240
29
46
22
181
138
13
21
87
47
85
28
18
261
14
65
212
33
193
109
130
225
32
105
80
151
93
222
53
68
38
129
103
34
101
157
30
96
216
118
194
133
60
90
88
123
10
15
155
184
73
119
75
54
70
171
187
2
248
127
35
59
239
84
23
79
121
99
40
250
3
76
176
221
41
62
44
55
107
72
168
203
49
6...

output:

? 265 36
? 136 174
? 24 78
? 124 8
? 256 240
? 241 29
? 179 46
? 22 102
? 243 181
? 234 138
? 160 13
? 21 268
? 87 242
? 47 208
? 85 300
? 156 28
? 37 18
? 293 261
? 299 14
? 65 94
? 219 212
? 255 33
? 202 193
? 109 282
? 130 186
? 278 225
? 32 158
? 161 105
? 298 80
? 151 247
? 273 93
? 222 279
? 1...

result:

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

Test #69:

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

input:

300
15
88
146
141
31
8
75
197
131
10
73
95
151
16
14
43
180
28
175
85
67
196
96
5
226
152
23
91
168
122
79
50
118
70
159
173
137
46
199
83
119
206
207
135
25
38
41
167
240
68
34
6
94
143
80
187
13
139
129
76
184
40
153
117
115
221
87
261
29
51
92
126
142
201
258
164
84
19
113
202
65
81
21
150
208
13...

output:

? 225 246
? 251 120
? 102 55
? 71 4
? 172 255
? 101 16
? 112 194
? 209 118
? 67 36
? 297 40
? 45 130
? 234 90
? 185 284
? 85 51
? 258 64
? 63 81
? 83 186
? 60 215
? 96 156
? 241 184
? 155 175
? 294 57
? 144 151
? 222 232
? 107 5
? 72 162
? 127 98
? 285 150
? 279 259
? 167 132
? 300 42
? 22 278
? 166...

result:

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

Test #70:

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

input:

1000
40
193
627
902
59
35
250
18
165
224
65
430
549
536
622
191
229
31
112
69
261
802
57
576
814
46
144
312
800
240
326
12
135
400
150
277
33
158
805
172
237
41
609
628
98
141
19
675
390
159
855
680
66
348
420
341
36
437
289
200
457
345
192
716
173
295
97
516
694
131
220
3
163
244
43
504
338
475
506...

output:

? 986 863
? 744 963
? 775 972
? 799 444
? 909 739
? 556 467
? 336 334
? 498 952
? 892 458
? 631 119
? 891 806
? 55 14
? 839 337
? 958 861
? 570 601
? 710 517
? 399 211
? 126 539
? 538 45
? 803 934
? 296 655
? 56 643
? 5 668
? 965 261
? 79 289
? 779 542
? 460 834
? 359 620
? 901 796
? 443 519
? 652 8...

result:

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

Test #71:

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

input:

1000
294
230
1296
1239
1717
646
969
825
492
494
817
199
58
776
110
702
397
214
1015
420
334
100
115
915
253
443
1910
1116
77
1149
543
442
799
736
590
451
888
1469
1270
813
1085
1499
328
1845
1094
1335
709
1486
109
777
1042
532
207
715
237
1026
922
91
217
337
823
828
564
15
859
157
701
1146
711
231
3...

output:

? 586 154
? 122 890
? 666 802
? 634 814
? 859 876
? 337 862
? 498 867
? 670 425
? 966 258
? 711 260
? 791 420
? 101 878
? 500 37
? 398 619
? 315 64
? 364 608
? 205 240
? 133 113
? 938 522
? 219 833
? 173 662
? 58 549
? 67 194
? 471 576
? 135 893
? 231 276
? 951 977
? 573 668
? 44 571
? 591 998
? 287...

result:

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

Test #72:

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

input:

1000
85405
85453
85537
85632
85465
85679
85651
85595
85477
85783
85514
85491
85825
85515
85686
85615
85716
86010
85893
85798
85890
85710
85445
85577
85578
85939
86222
85634
85483
85584
85516
85482
85411
85941
85424
85767
85741
85561
85447
85822
85960
86078
85790
85485
86109
85765
85512
85880
85665
8...

output:

? 6 788
? 929 54
? 376 138
? 840 233
? 66 859
? 836 280
? 252 597
? 196 552
? 78 562
? 918 384
? 326 115
? 550 92
? 426 506
? 116 443
? 755 287
? 216 479
? 317 864
? 769 610
? 837 494
? 413 399
? 491 629
? 311 389
? 894 46
? 766 178
? 704 179
? 910 539
? 865 822
? 986 235
? 632 84
? 874 185
? 117 47...

result:

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

Test #73:

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

input:

1000
7431
5955
8531
5612
7993
8861
7562
6915
5271
7583
5633
6603
7158
6015
8336
6469
6584
6976
9177
8367
7620
7864
5713
7758
6985
6071
8517
6351
7374
6579
5588
6823
5444
8599
6430
5913
5381
5106
8850
7035
5170
8016
8890
6791
7469
6376
7452
5385
5544
6484
6258
6465
8247
7030
6687
8902
6494
7023
7182
...

output:

? 448 762
? 658 165
? 691 851
? 234 104
? 993 571
? 763 997
? 482 992
? 346 812
? 436 42
? 550 489
? 981 109
? 659 283
? 401 437
? 714 177
? 648 715
? 459 263
? 279 599
? 361 478
? 940 829
? 654 850
? 524 497
? 893 551
? 897 123
? 772 531
? 971 365
? 840 190
? 896 689
? 304 235
? 635 440
? 583 278
?...

result:

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

Test #74:

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

input:

1000
4163
4081
5960
5733
4249
4323
4707
4319
4011
5117
4565
4238
4414
4929
4080
4369
4463
4142
4893
4085
4458
4576
4958
5540
4461
5179
4628
5344
5842
5361
5696
4050
5053
4474
4434
4220
4036
4202
4532
4413
4644
4919
5640
4357
4266
4670
4095
4571
4368
4610
5171
4465
4948
5246
4938
5282
4455
4346
4191
...

output:

? 262 93
? 522 38
? 977 979
? 947 870
? 249 135
? 174 531
? 354 848
? 171 452
? 1000 7
? 708 556
? 278 382
? 781 127
? 245 216
? 784 463
? 37 809
? 200 474
? 875 237
? 78 471
? 446 859
? 51 40
? 233 696
? 713 286
? 820 476
? 810 765
? 443 235
? 594 831
? 414 315
? 676 844
? 974 919
? 702 683
? 847 9...

result:

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

Test #75:

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

input:

1000
65883
59763
65445
59408
60806
60598
56253
57834
63211
50227
50649
50825
62713
60568
62568
56608
62333
66165
61880
75005
52916
71629
58084
53224
53791
66432
62567
57473
69296
64289
65402
59788
55857
66444
52623
61864
75636
60829
55436
52548
51952
74977
77592
63219
66030
70535
60883
76475
62696
5...

output:

? 425 551
? 476 256
? 412 470
? 531 250
? 284 688
? 535 277
? 892 152
? 624 209
? 348 817
? 6 637
? 12 232
? 20 614
? 975 338
? 557 276
? 334 853
? 715 169
? 324 581
? 436 464
? 312 864
? 996 700
? 75 506
? 600 847
? 221 961
? 483 83
? 780 94
? 660 447
? 825 333
? 202 764
? 517 988
? 576 378
? 410 6...

result:

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

Test #76:

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

input:

1000
591
670
77
853
119
141
75
439
638
495
112
779
740
364
910
196
397
51
171
468
581
153
134
753
163
253
143
64
197
33
344
259
386
383
589
190
29
27
417
385
59
98
194
523
608
102
178
21
379
16
107
898
268
215
71
293
459
538
580
83
371
228
862
472
592
432
132
425
278
13
156
67
70
334
128
568
599
114...

output:

? 709 849
? 565 790
? 517 229
? 772 898
? 574 737
? 566 38
? 62 881
? 965 333
? 53 175
? 670 847
? 446 651
? 558 252
? 967 621
? 743 769
? 848 19
? 817 602
? 813 160
? 407 174
? 883 272
? 408 70
? 45 809
? 28 278
? 239 981
? 782 615
? 64 529
? 213 991
? 952 298
? 509 789
? 381 273
? 569 630
? 937 59...

result:

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

Test #77:

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

input:

1000
693
389
633
754
1733
1014
87
351
1178
772
144
1251
1004
1644
1507
246
918
1012
400
341
688
740
1109
1379
24
1246
296
504
1217
201
254
129
380
111
194
1858
586
109
1625
946
869
319
243
249
1349
1459
1148
456
1955
274
117
1376
481
871
21
175
16
158
781
93
493
793
1630
1029
614
1186
430
651
678
84...

output:

? 275 784
? 168 907
? 645 80
? 333 129
? 332 886
? 555 590
? 313 114
? 226 752
? 477 334
? 253 415
? 441 666
? 115 962
? 625 201
? 166 184
? 551 935
? 883 612
? 443 300
? 462 273
? 331 897
? 62 4
? 715 469
? 979 775
? 224 136
? 290 583
? 195 795
? 135 379
? 975 552
? 447 231
? 770 60
? 930 489
? 846...

result:

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

Test #78:

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

input:

1000
85427
85462
85404
85770
85789
86163
85730
86336
85564
85794
85497
85976
85694
85573
85783
85735
86150
85841
85543
85422
86084
85586
86223
85549
85441
85432
85411
85508
86185
85820
85539
86156
85858
85985
85896
85423
85828
86091
86206
85620
86000
85583
85575
85602
85915
85831
85493
85646
85966
8...

output:

? 90 257
? 806 128
? 261 12
? 210 585
? 718 420
? 21 268
? 126 393
? 98 818
? 696 722
? 945 41
? 597 374
? 870 586
? 91 750
? 723 984
? 787 638
? 150 427
? 623 598
? 256 542
? 776 902
? 125 465
? 752 847
? 70 386
? 245 399
? 457 857
? 541 963
? 610 828
? 527 905
? 519 115
? 755 650
? 66 835
? 5 142
...

result:

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

Test #79:

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

input:

1000
5266
7169
6837
6062
5593
5446
6152
6939
6421
5501
5740
6507
5053
8870
6108
6253
6357
6039
5732
7233
6805
6775
9277
6924
5760
6733
6374
5056
7371
6292
5419
7908
9539
7477
6438
6007
5061
8414
8082
5281
7029
6839
7491
5402
5752
5431
6444
5447
8189
6757
7278
5665
6460
7381
5962
5433
8182
7974
5198
...

output:

? 96 632
? 809 796
? 645 649
? 765 714
? 444 423
? 609 315
? 636 870
? 642 952
? 867 395
? 11 403
? 726 381
? 735 563
? 49 881
? 780 476
? 750 546
? 982 872
? 897 179
? 903 237
? 509 213
? 683 220
? 670 744
? 535 917
? 995 681
? 123 601
? 21 861
? 948 7
? 481 831
? 419 784
? 884 222
? 452 773
? 342 ...

result:

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

Test #80:

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

input:

1000
4846
4148
4357
4689
4293
5294
4555
4909
4484
4043
4394
4166
4559
4345
4316
5258
5849
4883
5147
5638
4544
4128
4535
4200
5344
4851
5051
4786
4487
5736
4320
4140
5469
4082
5209
5319
4154
5430
4750
4907
4124
4836
4220
5088
4267
4315
4965
5227
4194
5061
4089
4070
5549
4864
4607
4621
5586
5262
5188
...

output:

? 884 74
? 562 354
? 273 730
? 656 653
? 858 397
? 150 839
? 808 128
? 186 323
? 694 664
? 724 844
? 787 891
? 206 992
? 742 832
? 632 197
? 700 107
? 193 629
? 38 343
? 516 895
? 643 138
? 412 548
? 247 363
? 655 596
? 518 170
? 776 115
? 929 754
? 448 305
? 825 671
? 797 901
? 889 789
? 368 875
? ...

result:

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

Test #81:

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

input:

1000
54218
70632
60159
58515
50251
74162
72192
70758
53916
56505
69370
51186
55373
53389
61058
78826
71092
59755
51627
57518
68254
62895
72204
51929
55255
58512
51978
58631
80434
67616
52413
51012
66137
64393
67519
55880
78843
67992
67843
64675
56834
54878
53984
63406
77248
51130
75249
50618
63444
5...

output:

? 938 26
? 263 711
? 980 464
? 241 316
? 725 333
? 854 296
? 726 718
? 799 239
? 255 744
? 151 291
? 86 372
? 508 361
? 195 356
? 642 601
? 911 647
? 899 964
? 139 560
? 222 623
? 674 449
? 557 228
? 105 98
? 328 764
? 454 435
? 111 829
? 998 543
? 963 376
? 315 954
? 927 715
? 321 267
? 661 710
? 3...

result:

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

Test #82:

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

input:

1000
705
45
420
396
885
161
688
452
123
615
663
566
231
304
606
279
592
507
404
126
489
230
675
492
861
647
5
259
863
8
282
478
71
640
644
329
84
779
839
86
533
440
138
504
152
428
205
442
261
31
112
718
414
313
467
185
797
66
30
541
290
583
990
36
316
649
41
267
34
4
235
418
177
297
720
134
370
372...

output:

? 705 829
? 807 45
? 420 730
? 828 396
? 2 885
? 161 277
? 688 972
? 452 714
? 413 123
? 623 615
? 663 745
? 660 566
? 231 609
? 304 434
? 781 606
? 657 279
? 592 713
? 507 761
? 404 463
? 633 126
? 489 858
? 230 285
? 675 684
? 946 492
? 967 861
? 647 676
? 509 5
? 685 259
? 863 901
? 8 611
? 282 6...

result:

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

Test #83:

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

input:

1000
708
179
45
512
320
243
196
10
444
388
40
54
36
779
208
284
42
662
5
206
265
348
759
213
230
68
615
795
740
190
369
41
395
567
69
161
709
191
256
76
441
692
547
334
500
217
88
434
30
137
145
100
416
842
29
352
790
3
404
96
282
300
490
499
18
383
702
407
142
589
301
523
182
565
545
324
168
518
20...

output:

? 708 809
? 179 738
? 983 45
? 512 872
? 925 320
? 325 243
? 196 950
? 10 202
? 444 505
? 388 626
? 40 588
? 54 962
? 36 701
? 779 879
? 364 208
? 456 284
? 42 210
? 804 662
? 5 165
? 548 206
? 390 265
? 449 348
? 965 759
? 917 213
? 230 356
? 969 68
? 615 654
? 818 795
? 740 958
? 190 632
? 369 927...

result:

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

Test #84:

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

input:

1000
477
303
587
151
782
221
431
2
326
46
85
67
599
153
130
339
404
398
408
202
218
428
250
325
756
419
7
567
672
278
667
40
436
72
660
160
576
89
113
526
238
943
135
714
240
252
71
844
98
308
406
86
125
242
369
61
279
581
841
595
177
534
18
306
145
68
629
299
170
734
58
84
478
704
462
631
117
710
4...

output:

? 207 967
? 825 48
? 551 702
? 251 839
? 721 794
? 446 1
? 887 541
? 275 666
? 951 927
? 938 94
? 931 533
? 886 233
? 850 757
? 616 298
? 343 669
? 123 624
? 873 530
? 813 13
? 140 155
? 779 332
? 124 532
? 252 454
? 287 339
? 113 257
? 697 348
? 358 431
? 858 741
? 944 152
? 544 588
? 974 148
? 547...

result:

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

Test #85:

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

input:

1000
659
280
70
73
313
374
695
556
320
179
213
519
378
228
182
226
10
292
245
475
87
321
174
55
420
432
5
43
363
753
362
186
298
473
387
256
398
690
674
192
551
308
208
860
361
647
75
27
193
215
300
230
443
210
422
181
341
198
440
140
757
190
157
173
467
732
891
83
288
866
633
710
688
13
528
60
302
...

output:

? 659 977
? 280 614
? 495 70
? 989 73
? 313 706
? 785 374
? 976 695
? 556 908
? 320 562
? 179 966
? 513 213
? 656 519
? 500 378
? 816 228
? 379 182
? 226 791
? 472 10
? 466 292
? 245 681
? 475 642
? 718 87
? 321 525
? 174 326
? 55 574
? 437 420
? 432 823
? 5 957
? 43 400
? 363 687
? 753 998
? 532 36...

result:

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

Test #86:

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

input:

1000
496
303
720
262
84
397
543
215
17
484
118
121
108
757
814
838
31
278
144
364
16
693
806
454
76
96
469
294
390
223
345
63
255
325
432
208
725
183
457
91
346
33
525
61
146
704
556
110
151
825
507
499
9
393
538
285
55
429
318
74
767
102
25
235
261
603
367
306
271
158
438
405
451
73
89
663
169
607
...

output:

? 496 774
? 303 959
? 720 853
? 262 375
? 84 212
? 971 397
? 543 557
? 508 215
? 17 22
? 484 998
? 118 919
? 510 121
? 108 805
? 943 757
? 814 979
? 873 838
? 463 31
? 278 886
? 144 356
? 364 852
? 787 16
? 693 736
? 932 806
? 482 454
? 822 76
? 426 96
? 597 469
? 294 480
? 756 390
? 623 223
? 900 3...

result:

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

Test #87:

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

input:

1000
21
2
188
572
83
231
550
42
137
504
31
636
65
98
708
406
447
57
141
921
542
268
112
32
97
47
638
51
121
526
163
592
446
483
174
73
388
328
61
78
382
217
517
736
134
62
391
196
146
252
246
602
233
234
287
19
474
501
77
298
253
37
118
22
236
164
363
692
644
398
376
932
389
377
9
516
889
325
245
27...

output:

? 183 21
? 2 855
? 188 423
? 572 608
? 83 771
? 603 231
? 550 619
? 241 42
? 302 137
? 504 658
? 31 821
? 854 636
? 543 65
? 506 98
? 708 802
? 406 827
? 447 923
? 267 57
? 984 141
? 921 975
? 566 542
? 268 703
? 754 112
? 32 293
? 97 172
? 47 169
? 957 638
? 759 51
? 565 121
? 864 526
? 807 163
? 9...

result:

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

Subtask #3:

score: 33.8403
Acceptable Answer

Test #88:

score: 34.495
Acceptable Answer
time: 7ms
memory: 12764kb

input:

1500
563
167
515
51
706
561
166
183
1196
744
130
578
731
381
340
763
549
174
556
821
916
524
709
69
999
481
16
44
350
597
25
141
794
707
484
84
951
871
359
823
1245
269
295
77
546
610
1378
1341
180
638
94
885
406
602
722
877
271
644
801
933
1356
261
900
595
35
593
755
539
113
573
114
612
516
255
820...

output:

? 778 563
? 167 506
? 515 652
? 947 51
? 706 1106
? 1292 561
? 166 1477
? 967 183
? 1221 1196
? 744 1271
? 472 130
? 578 1465
? 731 732
? 1254 381
? 1096 340
? 763 1467
? 549 1296
? 417 174
? 556 901
? 821 998
? 916 934
? 524 566
? 1416 709
? 522 69
? 999 1305
? 481 889
? 16 1275
? 44 140
? 760 350
...

result:

points 0.43118791090 points  0.43118791090 n = 1500, you used 2570 queries

Test #89:

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

input:

1500
1097
855
1389
910
430
392
846
321
282
925
2
434
1128
396
300
508
1003
636
899
1098
958
117
288
88
547
1063
121
990
783
1111
61
316
453
489
219
751
858
729
133
93
366
35
293
211
183
1357
1121
174
1425
646
145
6
217
1029
928
194
243
619
1310
773
127
278
325
252
270
46
255
711
692
59
306
777
1055
...

output:

? 404 103
? 353 646
? 112 58
? 591 190
? 1071 479
? 1109 950
? 655 209
? 1180 225
? 1219 1044
? 316 576
? 1499 1410
? 600 1067
? 202 373
? 1105 885
? 94 1201
? 343 993
? 305 498
? 865 128
? 602 280
? 70 403
? 495 543
? 437 1384
? 1213 250
? 1413 860
? 954 442
? 185 438
? 871 1380
? 511 299
? 718 686...

result:

points 0.44329949410 points  0.44329949410 n = 1500, you used 2487 queries

Test #90:

score: 34.9639
Acceptable Answer
time: 11ms
memory: 12760kb

input:

1500
382
427
722
430
485
244
239
1166
860
954
136
597
1029
107
363
250
198
115
328
428
726
387
207
335
10
1141
120
929
754
277
1057
226
54
584
386
654
872
128
886
732
623
242
72
935
1177
27
643
168
958
112
856
45
199
813
812
53
306
188
809
180
513
70
35
193
1084
145
834
134
220
551
602
1086
952
60
6...

output:

? 851 1310
? 214 942
? 455 1140
? 1021 1286
? 243 600
? 1379 552
? 280 120
? 639 918
? 607 1071
? 536 1024
? 172 1433
? 299 679
? 515 885
? 474 54
? 1093 182
? 403 1376
? 1402 1340
? 691 58
? 219 1337
? 1287 1112
? 1138 642
? 1081 194
? 150 104
? 168 277
? 911 1496
? 654 571
? 325 1441
? 465 1017
? ...

result:

points 0.43704858960 points  0.43704858960 n = 1500, you used 2529 queries

Test #91:

score: 34.5063
Acceptable Answer
time: 14ms
memory: 12764kb

input:

1500
187
435
378
197
677
1154
609
52
1305
407
807
130
751
740
129
291
490
199
1037
1121
614
369
210
1034
1031
817
996
1078
959
405
387
45
358
109
1003
987
179
598
313
108
144
1044
141
854
992
1027
582
138
277
600
399
123
819
426
867
370
153
694
1076
1135
9
761
1067
1432
710
1279
663
877
823
126
764
...

output:

? 907 1407
? 1283 1276
? 189 1300
? 1402 1259
? 526 1162
? 577 680
? 1196 1133
? 26 523
? 719 848
? 553 1297
? 1097 831
? 918 65
? 1125 470
? 370 379
? 1436 113
? 151 1355
? 415 245
? 584 1401
? 794 982
? 940 892
? 307 1055
? 1316 510
? 105 1036
? 903 517
? 524 985
? 1040 1092
? 771 498
? 956 539
? ...

result:

points 0.43132816330 points  0.43132816330 n = 1500, you used 2569 queries

Test #92:

score: 33.8403
Acceptable Answer
time: 3ms
memory: 12728kb

input:

1500
1008
327
823
27
475
754
672
129
1184
18
513
722
965
93
839
550
62
20
656
50
86
394
442
298
472
450
962
416
903
279
1292
137
609
354
385
1111
352
444
668
573
507
60
924
726
1364
168
459
716
9
481
82
400
719
531
979
1133
757
877
149
201
493
6
864
68
972
288
439
824
330
255
725
274
580
96
61
146
1...

output:

? 247 1408
? 1273 914
? 1162 67
? 764 838
? 988 77
? 33 374
? 1160 415
? 1456 815
? 159 84
? 742 853
? 347 1007
? 390 7
? 1233 1362
? 463 797
? 1496 1170
? 14 476
? 1432 720
? 1415 741
? 119 423
? 726 1006
? 708 1463
? 554 240
? 360 530
? 602 1304
? 253 515
? 125 526
? 270 76
? 344 543
? 1423 1202
?...

result:

points 0.42300406320 points  0.42300406320 n = 1500, you used 2630 queries

Test #93:

score: 34.3169
Acceptable Answer
time: 4ms
memory: 12732kb

input:

1500
169
241
654
493
710
73
451
1137
509
745
983
313
736
209
718
123
29
830
758
633
753
100
928
867
646
221
488
917
569
604
253
998
1068
302
152
392
5
276
562
1055
181
1000
1087
456
615
588
158
53
330
595
281
947
1268
800
402
477
827
265
143
1053
866
52
508
503
215
837
950
761
546
346
1249
408
203
4...

output:

? 666 1347
? 1242 630
? 138 1077
? 504 1452
? 165 1105
? 1068 714
? 321 525
? 182 1477
? 26 496
? 326 378
? 36 259
? 594 1257
? 366 1118
? 167 646
? 1346 1109
? 689 1247
? 736 565
? 300 1165
? 276 1129
? 1334 434
? 374 296
? 800 621
? 1214 50
? 317 38
? 1073 1488
? 68 640
? 154 994
? 197 292
? 1261 ...

result:

points 0.42896152490 points  0.42896152490 n = 1500, you used 2586 queries

Test #94:

score: 34.6531
Acceptable Answer
time: 0ms
memory: 12648kb

input:

1500
118
291
38
469
4
112
585
716
1284
189
876
617
364
39
393
1292
390
487
35
869
92
787
743
748
1168
117
644
803
1045
418
791
467
1201
993
10
404
836
468
1323
569
1138
608
29
21
913
592
545
731
142
66
509
215
114
1414
656
234
277
584
91
373
1036
283
1416
956
670
370
1112
712
697
1104
212
692
481
56...

output:

? 1265 1209
? 919 182
? 1425 845
? 351 563
? 325 1493
? 690 1277
? 336 331
? 69 58
? 1250 1068
? 1123 186
? 406 252
? 670 267
? 773 1144
? 1342 1423
? 715 870
? 1084 1392
? 721 16
? 1034 527
? 1476 1431
? 238 968
? 1118 1317
? 562 74
? 15 998
? 84 5
? 954 836
? 1267 227
? 772 213
? 106 762
? 1452 59...

result:

points 0.43316348040 points  0.43316348040 n = 1500, you used 2556 queries

Test #95:

score: 36.1134
Acceptable Answer
time: 6ms
memory: 12700kb

input:

1500
174
399
56
606
59
1092
72
344
46
898
579
839
420
123
588
385
773
485
95
585
611
74
428
621
583
69
442
335
808
36
539
296
122
308
100
28
895
405
396
259
495
162
1032
110
604
278
1284
224
1143
117
242
93
209
524
212
1028
966
423
981
417
305
916
415
717
716
976
16
147
748
1371
517
580
918
228
749
...

output:

? 348 1373
? 798 1168
? 112 500
? 77 1212
? 602 118
? 817 379
? 288 144
? 1311 688
? 92 312
? 1205 465
? 1158 135
? 849 1323
? 1162 840
? 246 773
? 657 1176
? 1033 770
? 477 1455
? 743 970
? 29 190
? 1170 973
? 1222 529
? 513 148
? 856 1058
? 1242 941
? 1166 189
? 1221 138
? 1082 884
? 663 670
? 138...

result:

points 0.45141802060 points  0.45141802060 n = 1500, you used 2435 queries

Test #96:

score: 34.54
Acceptable Answer
time: 6ms
memory: 12644kb

input:

1500
365
423
101
1051
260
748
566
106
763
120
707
563
311
80
150
350
1339
541
6
987
1027
1196
390
1199
60
419
425
1054
936
392
69
81
1251
389
47
287
43
804
127
726
694
221
377
330
71
5
971
448
10
526
343
456
750
817
349
344
849
1058
612
256
244
299
1141
1083
278
140
30
136
129
874
1077
951
670
555
4...

output:

? 364 587
? 1332 422
? 100 732
? 1165 1050
? 261 1341
? 1159 749
? 567 878
? 107 901
? 936 762
? 1254 121
? 783 706
? 1060 562
? 310 923
? 81 1218
? 151 631
? 1113 351
? 1338 1424
? 540 1041
? 702 7
? 986 1495
? 1033 1026
? 1197 1240
? 391 1492
? 1323 1198
? 61 685
? 608 418
? 424 818
? 1055 1056
? ...

result:

points 0.43174970930 points  0.43174970930 n = 1500, you used 2566 queries

Test #97:

score: 36.0622
Acceptable Answer
time: 16ms
memory: 12692kb

input:

1500
823
259
101
21
406
976
1054
668
20
132
291
26
599
137
781
1178
156
461
153
444
915
722
262
436
311
181
1043
727
18
127
1003
1451
306
982
350
22
735
87
196
302
593
862
236
1110
1316
1387
323
522
172
713
1183
961
1211
7
79
430
405
102
617
1184
46
298
235
481
463
1242
526
268
661
34
918
747
1275
8...

output:

? 335 679
? 1243 1133
? 1401 779
? 1481 353
? 716 1094
? 15 524
? 446 205
? 832 105
? 158 1480
? 1186 1368
? 107 1211
? 1474 157
? 289 903
? 488 1365
? 721 186
? 145 322
? 1344 719
? 530 1041
? 1349 511
? 884 1056
? 587 375
? 778 590
? 1238 790
? 263 1064
? 1191 341
? 1321 403
? 430 459
? 775 740
? ...

result:

points 0.45077767810 points  0.45077767810 n = 1500, you used 2439 queries

Test #98:

score: 35.8846
Acceptable Answer
time: 7ms
memory: 12668kb

input:

1500
355
440
281
942
1134
461
414
99
724
534
512
92
417
515
706
836
522
434
128
792
890
992
462
98
647
117
76
155
6
353
358
164
806
237
65
457
195
253
438
105
193
256
171
912
447
931
1098
191
624
213
266
116
735
169
190
881
1192
715
162
233
181
53
763
320
367
1164
215
379
21
217
765
784
55
1086
571
...

output:

? 1480 500
? 454 1440
? 882 644
? 509 904
? 227 1347
? 659 1446
? 789 918
? 143 40
? 1212 953
? 615 1125
? 877 378
? 931 135
? 535 746
? 1241 570
? 790 788
? 465 251
? 122 752
? 29 1403
? 643 821
? 1327 787
? 1417 1377
? 874 1208
? 448 1044
? 131 666
? 1120 370
? 367 1188
? 739 909
? 703 1134
? 1423...

result:

points 0.44855776450 points  0.44855776450 n = 1500, you used 2453 queries

Test #99:

score: 36.1006
Acceptable Answer
time: 22ms
memory: 12628kb

input:

1500
599
480
1125
887
402
174
684
80
617
313
715
15
140
254
678
169
73
629
977
381
886
1066
1228
48
240
1074
405
1023
612
792
247
549
1073
876
215
702
602
1462
510
1147
51
132
272
751
222
449
976
61
705
368
967
752
407
108
67
72
158
836
36
227
729
718
117
370
338
431
944
486
286
62
291
64
267
162
31...

output:

? 692 1331
? 835 1097
? 636 1101
? 1168 1408
? 582 763
? 1011 1295
? 349 1259
? 546 960
? 1149 214
? 1071 912
? 638 131
? 1351 360
? 446 895
? 102 1319
? 1498 1238
? 380 1025
? 1160 1103
? 1086 1246
? 416 690
? 877 702
? 1184 324
? 397 850
? 1130 287
? 211 678
? 560 298
? 355 738
? 24 718
? 847 1345...

result:

points 0.45125767850 points  0.45125767850 n = 1500, you used 2436 queries

Test #100:

score: 35.0693
Acceptable Answer
time: 0ms
memory: 12728kb

input:

1500
1133
658
1184
849
758
721
116
469
656
653
403
246
682
230
450
104
580
618
339
1330
609
308
843
546
652
164
497
699
1143
612
10
934
696
297
14
202
46
13
32
272
372
342
633
259
177
337
724
222
490
333
101
432
208
334
288
624
38
889
1083
1306
7
1215
96
211
1036
520
300
61
1240
1047
655
231
415
236...

output:

? 1438 1163
? 1309 1083
? 1138 705
? 1010 360
? 1248 1045
? 1245 341
? 1338 484
? 1300 1255
? 106 774
? 595 988
? 1353 146
? 1306 816
? 40 383
? 1433 205
? 1340 1106
? 72 348
? 1082 168
? 1427 164
? 768 265
? 894 681
? 1021 777
? 1238 1434
? 1307 953
? 468 699
? 765 58
? 435 528
? 890 446
? 119 327
...

result:

points 0.43836631410 points  0.43836631410 n = 1500, you used 2520 queries

Test #101:

score: 34.5625
Acceptable Answer
time: 7ms
memory: 12732kb

input:

1500
1644
36
1630
1036
159
324
697
1648
2118
1809
1905
1010
1056
595
1771
618
607
23
1008
1062
1402
814
603
694
22
2518
1259
1947
1091
1611
137
37
1956
654
1494
886
1162
1704
857
1371
401
234
1549
177
390
545
180
2285
570
918
549
1180
239
1228
1990
265
1128
1164
347
158
874
1997
927
575
1086
1367
82...

output:

? 829 852
? 19 136
? 822 1307
? 1455 519
? 78 402
? 166 407
? 346 608
? 1158 833
? 1054 1309
? 1103 910
? 951 1360
? 1403 503
? 528 560
? 699 292
? 1101 886
? 305 1444
? 299 676
? 13 1157
? 1355 501
? 529 720
? 925 701
? 399 1298
? 296 1178
? 343 455
? 1036 12
? 1257 1385
? 629 1104
? 1277 971
? 544...

result:

points 0.43203139950 points  0.43203139950 n = 1500, you used 2564 queries

Test #102:

score: 34.7673
Acceptable Answer
time: 3ms
memory: 12944kb

input:

1500
85276
85382
85632
85290
85554
85059
86017
86103
85704
85851
85703
85847
84927
85787
84979
85075
85459
85080
85127
84920
85285
84953
84908
85035
85920
85325
85125
85478
84932
85060
85672
85711
85144
84937
85565
84939
85107
85314
85358
85333
85272
85447
85482
85094
85221
84950
85330
85381
85819
8...

output:

? 1301 377
? 482 1215
? 732 788
? 391 549
? 927 654
? 160 1225
? 1117 1366
? 1458 1203
? 830 804
? 1007 951
? 803 883
? 947 1152
? 955 28
? 887 1490
? 80 390
? 281 176
? 559 1344
? 629 181
? 753 228
? 1307 21
? 386 1353
? 54 278
? 1296 9
? 136 1157
? 1407 1020
? 662 425
? 226 827
? 980 578
? 33 1494...

result:

points 0.43459070330 points  0.43459070330 n = 1500, you used 2546 queries

Test #103:

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

input:

1500
6548
6456
7982
7006
7223
8782
6011
6301
7130
8729
7788
5382
5780
6829
7835
7649
6381
8322
5779
5184
6447
6593
6092
8952
6990
7293
6900
7685
5850
5098
7052
5125
7334
6718
7140
5156
5177
6796
7168
6374
8820
8776
5535
5406
7302
5090
5921
8356
9481
6345
5109
6640
6545
5977
5056
8611
7817
5144
5627
...

output:

? 487 665
? 1364 455
? 1340 919
? 624 1187
? 697 1258
? 1149 1262
? 752 310
? 400 959
? 670 861
? 1136 1335
? 856 1283
? 251 128
? 567 232
? 775 569
? 960 875
? 806 1274
? 432 535
? 1395 1026
? 231 549
? 754 54
? 745 452
? 1115 503
? 413 330
? 1201 1485
? 1230 618
? 855 712
? 1334 591
? 823 886
? 12...

result:

points 0.43487778470 points  0.43487778470 n = 1500, you used 2544 queries

Test #104:

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

input:

1500
5765
5156
4160
4420
4751
5137
4494
4016
4684
5350
4966
4973
4044
4803
4003
4185
4873
4106
4395
4079
5418
4825
5800
4164
4291
4616
5326
5713
4081
4009
4072
5026
4630
4801
4320
4286
5648
4587
4931
5174
5130
4534
4770
4337
5085
5003
5100
4480
5880
4139
4648
5294
5028
4759
4381
5143
5119
4133
5541
...

output:

? 1467 1317
? 874 1082
? 126 377
? 1302 321
? 569 873
? 858 1318
? 375 500
? 14 286
? 518 575
? 1014 1086
? 1394 724
? 730 1328
? 36 449
? 603 928
? 3 1264
? 145 731
? 946 648
? 83 398
? 1076 304
? 64 1440
? 1325 1059
? 619 838
? 1397 1341
? 283 129
? 495 227
? 782 466
? 994 1288
? 1347 1279
? 1333 ...

result:

points 0.43559790130 points  0.43559790130 n = 1500, you used 2539 queries

Test #105:

score: 34.8594
Acceptable Answer
time: 3ms
memory: 12764kb

input:

1500
50581
60372
67499
66782
51847
59601
52083
57312
61060
64474
65807
52909
63217
51844
84965
57469
55288
50711
66966
72674
51846
59344
58890
71821
60590
68904
77008
68328
67316
50443
55584
52863
56790
59329
50047
63305
56871
51138
67223
52637
58183
69664
50947
58918
54770
56588
59452
62928
50079
6...

output:

? 1481 38
? 454 1139
? 1075 752
? 723 846
? 1143 95
? 427 821
? 322 102
? 1467 332
? 1261 484
? 1137 624
? 679 1235
? 141 810
? 888 559
? 93 326
? 1477 1446
? 336 490
? 243 662
? 50 1027
? 728 1297
? 978 1106
? 94 296
? 415 1195
? 451 399
? 1412 943
? 1085 464
? 924 817
? 1147 1475
? 790 1036
? 747 ...

result:

points 0.43574234040 points  0.43574234040 n = 1500, you used 2538 queries

Test #106:

score: 35.5371
Acceptable Answer
time: 9ms
memory: 12740kb

input:

1500
982
929
630
211
113
291
1028
137
420
141
106
631
93
281
98
1065
31
1221
219
578
816
121
232
401
353
51
1014
1191
874
430
643
380
294
28
373
880
586
442
180
393
580
55
704
536
893
123
351
488
332
194
177
309
67
7
370
347
588
585
677
66
142
655
492
433
197
101
810
209
605
435
582
429
654
391
1000...

output:

? 1150 908
? 1363 1114
? 78 326
? 936 576
? 1013 526
? 1230 1030
? 979 336
? 88 1075
? 1437 588
? 320 355
? 884 1163
? 45 1470
? 1143 650
? 1167 391
? 828 573
? 424 858
? 940 107
? 39 1262
? 514 162
? 414 528
? 215 368
? 1386 28
? 764 235
? 591 615
? 1472 1458
? 1415 333
? 485 1252
? 727 1451
? 700 ...

result:

points 0.44421413110 points  0.44421413110 n = 1500, you used 2481 queries

Test #107:

score: 35.8972
Acceptable Answer
time: 20ms
memory: 12688kb

input:

1500
769
114
440
196
667
1509
274
157
447
1297
426
1166
792
139
64
172
402
1167
1387
313
187
518
536
1022
487
45
314
455
824
513
1564
388
183
1118
306
169
1682
406
232
380
562
514
62
1373
1123
543
121
996
1188
1688
639
1868
733
567
214
255
753
94
1364
858
282
269
791
618
14
25
158
182
362
283
1060
9...

output:

? 1352 1495
? 767 1365
? 1152 854
? 452 244
? 21 404
? 629 634
? 375 557
? 1313 968
? 545 952
? 888 470
? 1 1183
? 1298 133
? 625 262
? 525 975
? 1266 1051
? 1471 1041
? 128 809
? 157 145
? 177 229
? 1094 491
? 1095 773
? 207 480
? 1038 533
? 1236 182
? 64 529
? 264 263
? 1029 1296
? 47 421
? 1019 2...

result:

points 0.44871524480 points  0.44871524480 n = 1500, you used 2452 queries

Test #108:

score: 35.5494
Acceptable Answer
time: 10ms
memory: 12664kb

input:

1500
85733
86114
85272
86097
86021
85540
85444
84961
84964
85142
84994
85275
84915
85509
85351
86127
85591
85611
85171
85427
85091
85287
85332
85814
84938
84960
85117
86037
85024
85410
84920
85559
85711
85265
85568
85474
85577
84939
84999
85931
86027
85042
85873
85243
85960
85145
85296
86148
85161
8...

output:

? 686 310
? 1327 701
? 813 817
? 1485 1378
? 1486 53
? 689 730
? 469 679
? 1182 279
? 443 299
? 235 861
? 760 327
? 1214 1324
? 449 806
? 1362 702
? 222 647
? 1273 1372
? 341 1229
? 968 694
? 35 659
? 283 287
? 905 1445
? 264 602
? 839 587
? 159 460
? 1345 721
? 1211 808
? 552 1495
? 802 145
? 103 8...

result:

points 0.44436711430 points  0.44436711430 n = 1500, you used 2480 queries

Test #109:

score: 35.7718
Acceptable Answer
time: 5ms
memory: 12636kb

input:

1500
5891
5834
6374
6245
8222
8818
5443
6839
5193
5849
5777
7362
8254
5607
7111
8767
8423
6287
5316
6252
6002
7668
5808
5868
5221
7359
5092
6515
5731
5364
5168
5949
5802
6572
6197
5736
5780
6687
7578
5577
5831
5105
6418
9460
5770
5860
8904
7024
7628
7112
7484
9785
9452
6018
5424
5578
6656
6812
9890
...

output:

? 576 1238
? 995 1121
? 101 616
? 1356 732
? 823 1463
? 1342 862
? 45 236
? 740 730
? 328 392
? 646 470
? 1364 1015
? 254 1188
? 949 792
? 374 1128
? 941 1035
? 359 719
? 687 283
? 1129 544
? 491 1148
? 843 189
? 336 1416
? 442 928
? 300 449
? 1025 481
? 414 1074
? 230 617
? 1419 27
? 500 1357
? 106...

result:

points 0.44714783240 points  0.44714783240 n = 1500, you used 2462 queries

Test #110:

score: 35.5371
Acceptable Answer
time: 5ms
memory: 12760kb

input:

1500
4531
5260
5399
4991
4416
4260
4594
4282
4729
4162
4274
4092
4284
5122
5412
5077
4351
5293
4001
5169
5591
4130
4084
4924
4050
5328
4361
4667
5450
4542
4452
4842
4703
4402
5756
4235
4573
4144
5261
5414
4650
5148
5102
4034
5650
5253
4674
4244
5315
4165
5048
5047
5168
4810
4227
5029
4947
5303
5610
...

output:

? 203 528
? 1358 1132
? 510 806
? 905 707
? 1350 339
? 400 821
? 1369 950
? 357 1127
? 1233 499
? 136 421
? 149 180
? 1005 875
? 1057 693
? 903 31
? 940 5
? 1336 322
? 1345 1087
? 603 113
? 580 85
? 445 833
? 786 822
? 365 464
? 626 207
? 429 1220
? 963 1114
? 1082 491
? 1411 1429
? 1416 338
? 937 4...

result:

points 0.44421413110 points  0.44421413110 n = 1500, you used 2481 queries

Test #111:

score: 36.0239
Acceptable Answer
time: 4ms
memory: 12688kb

input:

1500
55245
68828
70671
61298
62126
53148
60002
74565
59917
59770
67338
55546
68164
69011
70618
57288
57962
73284
63773
69393
77176
63221
52887
56708
54684
58652
50450
68708
62784
63106
73966
74599
55571
53486
79914
54689
53093
66336
52318
78705
54217
61897
74142
69684
62000
52227
83439
63209
58288
7...

output:

? 64 489
? 299 1351
? 790 28
? 514 1436
? 1381 122
? 537 1153
? 994 874
? 1310 538
? 90 814
? 457 477
? 1408 751
? 1241 1378
? 433 324
? 1336 1121
? 1103 694
? 217 1426
? 966 791
? 474 254
? 615 837
? 1169 487
? 668 1117
? 1110 406
? 834 627
? 247 796
? 1073 151
? 242 802
? 711 1181
? 1325 81
? 767 ...

result:

points 0.45029920880 points  0.45029920880 n = 1500, you used 2442 queries

Test #112:

score: 34.4503
Acceptable Answer
time: 2ms
memory: 12852kb

input:

1500
201
66
155
70
92
273
748
152
299
393
825
799
646
656
53
610
125
1184
1234
103
968
1076
408
682
444
538
425
654
1128
61
878
182
588
807
399
283
755
490
20
945
102
763
90
224
1090
1174
4
789
655
1010
367
211
583
645
628
220
149
694
91
634
389
236
574
834
255
976
727
712
32
637
1287
100
69
318
651...

output:

? 1371 201
? 1219 66
? 715 155
? 1004 70
? 92 927
? 273 1214
? 748 1178
? 985 152
? 299 346
? 1136 393
? 1121 825
? 1294 799
? 646 1181
? 1133 656
? 53 145
? 1444 610
? 432 125
? 1184 1353
? 1310 1234
? 103 1481
? 968 1024
? 1076 1411
? 408 852
? 682 841
? 798 444
? 538 760
? 425 1344
? 654 709
? 11...

result:

points 0.43062820870 points  0.43062820870 n = 1500, you used 2574 queries

Test #113:

score: 35.331
Acceptable Answer
time: 8ms
memory: 12632kb

input:

1500
922
513
359
171
9
1236
788
511
785
30
735
217
23
1076
222
194
40
399
236
437
318
1138
234
295
169
187
47
421
84
237
565
1089
196
857
3
476
805
508
1192
627
439
804
1166
18
86
1314
385
499
395
223
249
207
507
555
287
608
954
433
1141
866
1016
743
201
781
253
50
727
1286
560
912
398
71
1467
256
3...

output:

? 1084 922
? 513 1402
? 359 1269
? 171 442
? 9 606
? 1309 1236
? 1231 788
? 511 1223
? 1408 785
? 1435 30
? 735 1246
? 509 217
? 23 1364
? 1204 1076
? 1087 222
? 194 212
? 40 1215
? 399 1384
? 1441 236
? 437 862
? 318 1394
? 1138 1493
? 234 381
? 295 650
? 590 169
? 187 1108
? 47 281
? 701 421
? 84 ...

result:

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

Test #114:

score: 35.6601
Acceptable Answer
time: 7ms
memory: 12640kb

input:

1500
237
144
230
737
53
203
1022
526
685
379
1269
949
1062
354
419
458
1209
204
483
102
49
41
361
188
456
54
1016
190
315
126
176
1036
145
746
356
545
1166
780
407
32
214
150
283
24
363
714
344
279
1237
686
236
881
248
205
34
440
392
760
251
299
675
891
55
988
118
889
1155
919
444
365
187
293
3
348
...

output:

? 320 515
? 69 456
? 199 1363
? 1345 1251
? 418 995
? 326 224
? 889 1061
? 207 1440
? 665 277
? 1082 4
? 1392 532
? 1004 1002
? 1154 1323
? 403 1128
? 1090 520
? 858 1239
? 1340 20
? 982 788
? 822 439
? 1464 640
? 1244 661
? 1108 733
? 1349 887
? 922 364
? 801 588
? 1393 1342
? 259 959
? 779 655
? 6...

result:

points 0.44575102980 points  0.44575102980 n = 1500, you used 2471 queries

Test #115:

score: 34.3501
Acceptable Answer
time: 7ms
memory: 12688kb

input:

1500
582
972
239
403
382
822
341
705
417
577
559
624
1084
490
289
1111
244
362
357
547
847
514
739
260
160
1280
78
636
136
817
300
1258
313
187
673
744
536
258
813
449
11
901
617
268
152
936
74
1089
366
175
921
623
363
869
777
516
529
870
1008
84
307
169
17
290
463
328
528
850
1003
508
451
43
533
59...

output:

? 582 586
? 1000 972
? 1478 239
? 1445 403
? 382 958
? 960 822
? 341 630
? 818 705
? 417 1233
? 577 748
? 559 767
? 1001 624
? 1084 1198
? 490 501
? 289 1097
? 1111 1499
? 1103 244
? 939 362
? 357 554
? 568 547
? 847 1096
? 514 523
? 1257 739
? 260 1043
? 160 423
? 1301 1280
? 78 837
? 636 1207
? 33...

result:

points 0.42937646290 points  0.42937646290 n = 1500, you used 2583 queries

Test #116:

score: 34.8363
Acceptable Answer
time: 5ms
memory: 12648kb

input:

1500
638
1226
1124
40
449
96
156
709
69
417
97
256
370
381
187
467
1133
341
340
1063
105
384
799
311
844
375
176
876
1335
186
294
480
94
378
1281
1053
536
228
240
595
976
254
291
140
661
741
492
642
891
1014
723
15
196
423
296
208
368
963
736
994
439
632
931
780
358
4
792
1406
404
70
677
42
220
413
...

output:

? 1033 638
? 1357 1226
? 1124 1200
? 1458 40
? 449 1055
? 96 905
? 156 188
? 709 1498
? 69 1030
? 1426 417
? 1252 97
? 256 411
? 383 370
? 381 926
? 187 982
? 534 467
? 1272 1133
? 341 1042
? 340 1143
? 1170 1063
? 105 593
? 1340 384
? 1452 799
? 391 311
? 1431 844
? 964 375
? 641 176
? 876 1500
? 1...

result:

points 0.43545360120 points  0.43545360120 n = 1500, you used 2540 queries

Test #117:

score: 34.6644
Acceptable Answer
time: 3ms
memory: 12672kb

input:

1500
810
1001
641
154
1321
980
750
783
1
445
765
719
409
807
199
225
1201
709
398
1193
301
178
479
129
983
501
605
238
499
1094
834
820
215
287
51
767
143
320
777
337
71
876
1429
959
340
779
1084
214
1167
653
309
341
744
1030
489
167
359
3
280
600
456
363
393
611
504
218
206
230
49
408
119
185
37
62...

output:

? 986 810
? 1001 1309
? 768 641
? 154 243
? 1321 1438
? 1302 980
? 904 750
? 838 783
? 1499 908
? 1069 445
? 765 766
? 719 1188
? 409 1282
? 1161 807
? 1206 199
? 418 225
? 1201 1209
? 836 709
? 912 398
? 1286 1193
? 301 561
? 178 609
? 479 1435
? 129 347
? 983 1443
? 968 501
? 1419 605
? 238 1437
?...

result:

points 0.43330559310 points  0.43330559310 n = 1500, you used 2555 queries