QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765739#8267. Staring Contest_8_8_#52.629214 15ms12948kbC++204.4kb2024-11-20 15:08:552024-11-20 15:09:03

Judging History

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

  • [2024-11-20 15:09:03]
  • 评测
  • 测评结果:52.629214
  • 用时:15ms
  • 内存:12948kb
  • [2024-11-20 15:08:55]
  • 提交

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]});
    }
    shuffle(f.begin(), f.end(), rng);
    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: 2ms
memory: 12604kb

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #2:

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

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #3:

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

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

input:

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

output:

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

result:

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

Test #5:

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

input:

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

output:

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

result:

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

Test #6:

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

input:

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

output:

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

result:

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

Test #7:

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

input:

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

output:

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

result:

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

Test #8:

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

input:

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

output:

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

result:

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

Test #9:

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

input:

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

output:

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

result:

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

Test #10:

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

input:

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

output:

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

result:

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

Test #11:

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

input:

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

output:

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

result:

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

Test #12:

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

input:

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

output:

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

result:

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

Test #13:

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

input:

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

output:

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

result:

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

Test #14:

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

input:

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

output:

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

result:

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

Test #15:

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

input:

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

output:

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

result:

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

Test #16:

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

input:

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

output:

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

result:

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

Test #17:

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

input:

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

output:

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

result:

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

Test #18:

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

input:

50
86357
86367
86363
86354
86351
86382
86358
86368
86370
86392
86364
86352
86355
86374
86369
86381
86371
86350
86365
86360
86366
86353
86373
86361
86391
86379
86359
86366
86350
86368
86360
86383
86361
86390
86356
86371
86364
86392
86396
86370
86358
86369
86352
86372
86395
86389
86386
86384
86377
863...

output:

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

result:

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

Test #19:

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

input:

50
6824
5773
5914
7060
7026
9404
8939
8947
7993
5454
6109
5406
5302
8428
5813
6476
6926
6767
5076
8198
6099
6651
5703
7563
7159
7779
5454
7174
8098
8006
8060
8526
6375
9404
8939
8947
7663
5773
5813
6109
5406
7563
7060
5703
7993
9732
9491
8917
8464
8098
8006
7233
6297
7174
7779
8060
7026
6375
9032
96...

output:

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

result:

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

Test #20:

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

input:

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

output:

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

result:

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

Test #21:

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

input:

50
60767
53250
54962
50293
52428
74688
75306
82221
66090
56991
50918
73709
66780
75191
70891
58109
54556
61154
52604
56134
68459
77305
73877
56501
59551
65062
73877
77305
59551
73709
68459
52428
56134
80975
67638
66780
50918
56991
58109
66090
60767
61154
80336
75191
52604
70891
76687
50293
84766
847...

output:

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

result:

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

Test #22:

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

input:

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

output:

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

result:

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

Test #23:

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

input:

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

output:

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

result:

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

Test #24:

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

input:

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

output:

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

result:

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

Test #25:

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

input:

50
6181
5118
5252
8213
8495
8360
6614
5299
5503
6205
5171
5144
6722
5271
5141
9049
6553
5603
7553
6051
6461
7509
6327
5529
5310
5118
5252
7553
6850
6856
5310
7115
7405
5171
5603
6786
6553
8213
7215
6725
7829
8360
7509
5529
6181
9184
8741
5907
7115
9055
7205
7541
7405
7215
6786
8197
6850
7405
5907
67...

output:

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

result:

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

Test #26:

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

input:

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

output:

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

result:

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

Test #27:

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

input:

50
58357
51658
53454
54630
67146
72291
61968
57318
76101
62248
68422
53987
74083
65477
58746
67069
54250
58717
55504
61401
81710
79047
73863
70928
53213
80286
67005
58746
58717
72291
76101
70928
78154
79047
62248
67069
53213
79827
66448
72987
72620
79358
61968
77213
75023
76671
85096
71272
76671
824...

output:

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

result:

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

Test #28:

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

input:

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

output:

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

result:

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

Test #29:

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

input:

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

output:

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

result:

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

Test #30:

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

input:

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

output:

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

result:

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

Test #31:

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

input:

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

output:

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

result:

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

Test #32:

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

input:

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

output:

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

result:

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

Test #33:

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

input:

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

output:

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

result:

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

Test #34:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #35:

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

input:

4
2
3
3
2
5

output:

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

input:

4
5
2
3
3

output:

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

input:

4
3
2
2
5

output:

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

result:

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

Test #38:

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

input:

4
2
3
2
3
5

output:

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

result:

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

Test #39:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #40:

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

input:

4
3
2
3
2
5

output:

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

result:

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

Test #41:

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

input:

4
3
2
5

output:

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

result:

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

Test #42:

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

input:

4
2
5
2
3

output:

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

result:

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

Test #43:

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

input:

4
3
2
3
5
2

output:

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

result:

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

Test #44:

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

input:

4
2
3
5

output:

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

input:

4
3
2
2
3
5

output:

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

input:

4
2
5
2
3
3

output:

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

input:

4
2
3
2
5

output:

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

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 #49:

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

input:

4
2
5
3
3

output:

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

result:

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

Test #50:

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

input:

4
3
2
3
5

output:

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

input:

4
2
3
5

output:

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

result:

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

Test #52:

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

input:

4
2
3
3
2
5

output:

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

input:

4
5
2
2
3

output:

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

result:

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

Test #54:

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

input:

4
2
5
2
3
3

output:

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

result:

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

Test #55:

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

input:

4
2
3
5

output:

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

result:

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

Test #56:

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

input:

4
2
3
2
5
3

output:

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

result:

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

Test #57:

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

input:

4
5
2
2
3

output:

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

result:

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

Subtask #2:

score: 11
Accepted

Test #58:

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

input:

1000
504
261
176
316
137
383
224
672
6
166
420
276
28
7
956
592
240
132
140
351
454
254
72
298
433
600
466
519
220
77
73
30
486
94
226
429
207
452
562
721
211
238
480
481
391
42
196
887
413
46
743
35
730
769
56
447
22
465
563
533
289
297
8
611
312
190
222
858
156
438
350
200
210
11
621
512
448
205
6...

output:

? 588 504
? 468 261
? 367 176
? 970 316
? 362 137
? 383 443
? 416 224
? 726 672
? 6 320
? 166 202
? 420 596
? 276 961
? 28 49
? 551 7
? 995 956
? 906 592
? 335 240
? 746 132
? 140 604
? 351 692
? 865 454
? 254 979
? 765 72
? 585 298
? 929 433
? 1000 600
? 466 895
? 519 748
? 702 220
? 428 77
? 73 71...

result:

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

Test #59:

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

input:

1000
597
118
730
130
312
726
87
123
302
366
10
291
501
61
164
115
30
56
36
305
585
7
64
254
863
313
489
402
65
685
279
483
57
487
19
410
82
473
552
81
83
188
435
725
364
464
5
665
47
461
576
564
62
3
299
101
4
260
669
462
131
377
34
71
14
386
182
280
220
338
274
393
276
325
300
514
596
59
623
728
13...

output:

? 404 306
? 143 883
? 271 156
? 55 871
? 157 689
? 13 275
? 719 914
? 671 878
? 509 699
? 635 522
? 991 242
? 710 549
? 67 500
? 673 940
? 589 837
? 820 886
? 220 971
? 945 814
? 492 965
? 696 674
? 29 416
? 994 240
? 713 937
? 510 747
? 94 138
? 291 688
? 512 163
? 599 349
? 115 936
? 45 316
? 722 ...

result:

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

Test #60:

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

input:

1000
515
671
139
226
393
885
405
204
487
14
324
197
147
312
199
27
26
482
232
435
371
357
153
468
639
625
326
512
616
500
41
385
503
388
526
206
680
7
88
943
167
37
253
461
272
246
185
868
35
784
101
787
343
891
286
308
45
76
837
291
762
336
632
561
171
57
328
227
710
450
351
91
92
211
753
56
364
42...

output:

? 302 258
? 336 542
? 70 353
? 888 360
? 491 197
? 487 443
? 203 375
? 432 899
? 350 244
? 994 156
? 839 668
? 99 445
? 134 74
? 845 753
? 621 100
? 14 403
? 988 544
? 760 412
? 885 363
? 218 780
? 638 186
? 552 179
? 843 77
? 271 767
? 401 320
? 520 313
? 838 453
? 386 745
? 664 693
? 751 513
? 21 ...

result:

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

Test #61:

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

input:

1000
566
224
101
197
164
475
430
455
97
152
888
740
615
573
490
567
302
415
306
389
160
254
346
931
212
145
564
314
143
694
329
226
174
167
223
637
337
193
141
409
65
127
69
89
93
256
404
220
333
403
746
110
157
275
345
834
6
372
532
5
334
513
396
117
364
460
234
452
21
246
199
211
765
139
16
178
31...

output:

? 283 531
? 112 213
? 950 626
? 321 902
? 82 860
? 763 726
? 503 215
? 599 773
? 952 480
? 76 847
? 444 510
? 370 532
? 693 397
? 616 714
? 245 552
? 717 479
? 647 151
? 793 658
? 153 256
? 298 806
? 80 791
? 127 710
? 173 627
? 535 526
? 571 106
? 483 928
? 656 282
? 179 157
? 929 141
? 347 586
? 1...

result:

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

Test #62:

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

input:

1000
313
266
257
553
862
141
688
361
453
94
54
226
204
457
715
504
295
156
28
7
73
262
15
440
36
171
590
300
3
441
17
10
983
200
151
450
256
210
87
254
692
157
388
788
399
548
268
248
270
667
48
527
518
111
307
444
400
104
291
289
92
500
55
285
133
172
392
113
258
352
603
480
341
170
182
32
138
203
...

output:

? 657 915
? 368 309
? 629 324
? 985 777
? 59 70
? 304 571
? 157 898
? 681 760
? 792 727
? 454 651
? 474 831
? 388 225
? 320 399
? 82 729
? 960 858
? 85 249
? 648 737
? 423 660
? 487 963
? 932 504
? 537 31
? 370 353
? 508 216
? 281 27
? 872 483
? 586 861
? 206 54
? 351 812
? 545 502
? 205 721
? 268 5...

result:

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

Test #63:

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

input:

1000
345
193
60
269
787
232
300
74
805
115
415
151
186
85
420
291
15
210
308
422
277
17
559
383
344
350
743
846
26
206
173
436
442
59
772
334
329
190
100
290
673
465
321
227
376
306
234
176
165
256
536
207
457
405
751
61
228
158
112
661
91
155
358
110
593
620
585
747
409
1
913
505
757
148
197
174
28...

output:

? 802 328
? 404 373
? 137 530
? 366 133
? 107 958
? 616 838
? 288 650
? 537 145
? 90 98
? 443 897
? 751 293
? 842 425
? 593 251
? 601 458
? 779 710
? 355 788
? 804 493
? 605 128
? 327 654
? 234 711
? 362 42
? 24 492
? 843 221
? 309 981
? 101 672
? 675 313
? 965 129
? 941 923
? 513 658
? 603 729
? 41...

result:

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

Test #64:

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

input:

1000
171
309
196
165
619
147
61
538
440
633
154
226
3
102
176
45
563
479
593
486
407
672
340
351
170
74
173
338
181
556
76
32
687
157
97
51
581
559
519
428
901
225
830
88
507
90
202
231
891
268
851
24
22
390
437
1
12
86
235
99
161
273
371
431
250
521
321
253
186
82
175
363
316
385
215
614
536
565
62...

output:

? 659 882
? 610 383
? 355 609
? 286 671
? 238 926
? 707 123
? 879 324
? 76 820
? 236 121
? 266 662
? 693 642
? 517 549
? 133 995
? 602 797
? 605 649
? 911 698
? 704 126
? 43 322
? 186 894
? 392 29
? 342 187
? 450 344
? 321 922
? 590 299
? 661 288
? 853 608
? 655 640
? 325 16
? 639 116
? 112 480
? 54...

result:

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

Test #65:

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

input:

1000
444
572
308
369
298
217
171
371
809
684
55
192
393
93
680
304
744
116
671
346
590
60
132
274
161
92
732
216
59
62
65
36
111
286
313
88
64
215
44
285
448
117
197
525
344
277
249
269
398
146
546
144
162
243
163
700
283
81
567
222
936
19
176
288
350
761
90
268
842
126
497
85
140
256
202
295
361
94...

output:

? 888 91
? 857 431
? 616 670
? 738 231
? 596 159
? 434 922
? 342 560
? 5 742
? 383 99
? 515 633
? 110 847
? 384 543
? 786 859
? 186 573
? 641 137
? 567 608
? 325 513
? 555 232
? 659 405
? 692 561
? 821 475
? 253 120
? 264 808
? 548 851
? 322 891
? 923 184
? 351 537
? 775 432
? 123 118
? 124 393
? 13...

result:

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

Test #66:

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

input:

1000
433
9
217
481
404
245
638
209
16
468
498
366
42
274
452
307
297
122
135
13
370
102
378
121
474
649
89
778
111
123
365
748
556
195
562
349
475
220
236
449
136
235
5
90
570
181
227
572
501
276
439
152
690
226
198
44
336
156
763
176
142
82
360
653
744
263
258
592
144
25
381
246
436
151
255
194
408...

output:

? 764 432
? 8 892
? 216 925
? 706 480
? 405 620
? 465 244
? 639 799
? 736 208
? 17 828
? 469 578
? 499 816
? 367 845
? 43 983
? 275 804
? 755 453
? 306 951
? 296 811
? 203 123
? 134 224
? 12 696
? 643 371
? 103 580
? 379 618
? 120 703
? 475 728
? 648 776
? 88 955
? 779 975
? 889 110
? 122 782
? 528 ...

result:

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

Test #67:

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

input:

1000
538
637
320
490
648
242
397
399
486
687
36
174
913
445
649
614
369
262
119
443
106
52
546
167
412
2
9
797
442
208
200
274
462
505
603
159
171
492
85
408
653
595
98
178
128
121
40
58
640
574
241
100
197
10
195
32
452
65
430
187
120
94
372
261
234
496
196
220
358
21
73
15
401
588
605
62
679
398
1...

output:

? 248 462
? 206 365
? 680 81
? 421 510
? 352 313
? 279 758
? 326 605
? 452 603
? 242 514
? 233 315
? 964 173
? 458 826
? 4 89
? 557 80
? 255 353
? 386 40
? 633 275
? 738 368
? 883 576
? 559 200
? 894 328
? 948 871
? 316 454
? 757 835
? 219 588
? 988 998
? 993 537
? 205 35
? 558 542
? 290 792
? 800 7...

result:

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

Test #68:

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

input:

300
169
188
123
114
117
128
187
250
176
6
58
82
74
242
9
203
217
207
181
65
164
12
127
190
78
101
34
142
10
29
2
30
105
96
72
25
28
125
33
27
201
133
47
222
194
4
13
158
102
85
89
86
92
77
38
8
255
71
136
49
53
119
132
122
146
60
195
23
45
145
121
21
90
35
39
106
70
234
26
193
108
153
220
67
100
42
...

output:

? 265 169
? 188 260
? 131 123
? 114 170
? 238 117
? 128 271
? 187 199
? 250 296
? 176 182
? 6 129
? 58 268
? 103 82
? 74 98
? 242 278
? 55 9
? 237 203
? 253 217
? 207 227
? 206 181
? 241 65
? 164 292
? 95 12
? 155 127
? 190 261
? 239 78
? 101 262
? 34 290
? 286 142
? 10 41
? 29 73
? 91 2
? 30 285
? ...

result:

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

Test #69:

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

input:

300
157
11
97
66
25
187
98
173
276
120
168
5
4
108
77
65
18
155
75
51
82
61
3
52
35
231
252
194
21
228
132
28
79
184
233
116
222
93
141
170
90
103
121
172
87
14
47
175
100
186
89
27
182
117
94
134
15
2
242
137
127
33
56
37
22
203
60
101
161
73
46
179
152
49
30
200
57
131
136
250
19
17
135
64
177
95
...

output:

? 93 216
? 74 21
? 59 97
? 136 184
? 29 163
? 77 125
? 260 39
? 52 287
? 266 80
? 197 186
? 259 94
? 88 222
? 214 2
? 235 38
? 121 278
? 192 103
? 255 196
? 171 275
? 112 46
? 177 195
? 85 65
? 277 54
? 95 249
? 282 30
? 111 34
? 189 262
? 217 279
? 47 299
? 165 180
? 209 28
? 83 194
? 9 60
? 210 30...

result:

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

Test #70:

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

input:

1000
491
831
114
460
425
9
468
129
314
709
733
761
53
136
103
56
420
162
291
512
876
593
193
68
165
121
41
5
746
205
371
334
279
262
796
74
23
312
435
175
400
33
7
299
555
529
178
622
266
211
686
164
412
325
282
224
62
451
785
146
375
139
344
123
199
401
340
233
45
310
141
372
404
270
242
213
488
37...

output:

? 849 827
? 356 233
? 354 859
? 530 900
? 567 430
? 826 934
? 954 888
? 262 832
? 169 743
? 932 245
? 332 536
? 999 138
? 76 242
? 322 241
? 310 377
? 776 294
? 807 86
? 43 920
? 941 304
? 426 157
? 56 145
? 861 697
? 963 61
? 196 181
? 838 458
? 873 544
? 977 935
? 407 113
? 139 695
? 757 549
? 337...

result:

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

Test #71:

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

input:

1000
160
4
945
623
618
735
839
18
9
416
485
25
1936
591
20
555
616
1774
1266
885
1765
856
251
577
157
1094
1026
670
1102
349
1
12
443
293
102
974
467
1624
300
1120
159
252
1484
19
209
89
266
23
1345
1431
161
385
490
825
1494
1224
315
592
642
118
861
1705
1038
217
14
378
55
711
8
1295
988
726
701
871...

output:

? 84 383
? 2 376
? 485 555
? 324 439
? 901 321
? 841 381
? 920 432
? 12 825
? 892 5
? 708 216
? 315 255
? 18 730
? 996 967
? 307 370
? 14 509
? 523 293
? 320 617
? 919 880
? 648 792
? 668 458
? 876 883
? 475 441
? 715 133
? 300 667
? 82 310
? 561 824
? 529 657
? 348 658
? 709 566
? 182 720
? 662 1
?...

result:

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

Test #72:

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

input:

1000
85794
85809
86175
85547
85941
86134
85585
85983
85755
85515
85723
85462
85603
85848
86306
85947
85946
85935
85699
85617
85635
85523
85431
85530
85777
85604
86000
85432
85892
85655
85600
85455
85685
85450
85466
85902
86034
85687
85879
85673
86037
85718
85534
86054
85478
85485
85709
85858
85444
8...

output:

? 994 395
? 831 410
? 775 890
? 148 731
? 550 541
? 741 734
? 412 186
? 583 613
? 677 356
? 404 116
? 339 324
? 63 602
? 753 204
? 449 570
? 965 906
? 547 722
? 779 546
? 658 535
? 300 649
? 660 218
? 236 426
? 885 124
? 32 147
? 131 776
? 944 378
? 205 687
? 600 947
? 33 720
? 493 848
? 828 256
? 8...

result:

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

Test #73:

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

input:

1000
6907
5235
8457
7785
8612
5410
6687
5147
5641
6450
6722
7294
5851
7241
6604
8063
7096
7053
7058
5044
7641
5096
7696
6057
8446
7207
5013
6008
7864
7620
5521
6977
8821
8494
5079
5772
5426
5048
5104
5207
5980
8998
5957
8144
5553
7993
7149
6481
5998
7472
6821
5448
5728
6076
7595
8951
5098
6704
6870
...

output:

? 558 345
? 34 585
? 672 935
? 535 829
? 707 876
? 706 65
? 897 298
? 847 21
? 110 582
? 704 257
? 764 305
? 891 423
? 267 142
? 914 416
? 370 284
? 966 591
? 392 849
? 381 419
? 702 382
? 819 10
? 708 504
? 39 15
? 513 649
? 187 567
? 840 669
? 410 816
? 4 952
? 176 698
? 874 551
? 497 770
? 563 85...

result:

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

Test #74:

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

input:

1000
4267
4456
5362
4035
4320
4365
4200
4055
4722
4184
4332
4033
5107
4599
5148
5318
4432
4045
4702
4337
4644
4505
4080
4165
4311
4500
4727
4188
5530
4592
5092
5061
4561
4166
5236
5229
4308
4705
4568
5579
5695
4421
4239
4942
4440
5087
4029
4173
5817
4225
4002
5120
4378
4633
5632
4129
4016
4134
4738
...

output:

? 145 356
? 294 232
? 684 825
? 18 932
? 240 172
? 880 196
? 110 793
? 25 499
? 860 362
? 565 103
? 621 177
? 17 898
? 550 719
? 297 982
? 577 866
? 943 664
? 850 223
? 753 22
? 350 371
? 315 179
? 321 963
? 377 254
? 183 37
? 94 305
? 167 646
? 252 401
? 364 901
? 339 106
? 760 783
? 929 291
? 542 ...

result:

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

Test #75:

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

input:

1000
75573
55099
52208
68250
72196
58569
70441
69065
66528
54080
69677
76782
63851
61383
62159
70592
60994
69125
62134
59788
60568
50227
63719
58382
65687
54631
55085
56946
65445
55526
61874
51278
66506
75636
67884
66307
76584
60775
53050
62967
56608
58084
56157
56751
52762
66903
50649
57371
71582
5...

output:

? 721 754
? 125 375
? 145 54
? 927 495
? 646 621
? 700 229
? 857 566
? 560 513
? 453 947
? 104 305
? 531 884
? 924 758
? 362 774
? 302 411
? 472 321
? 572 629
? 292 354
? 515 703
? 390 318
? 329 257
? 276 485
? 6 281
? 360 881
? 911 225
? 420 526
? 869 114
? 123 261
? 180 258
? 412 524
? 133 772
? 6...

result:

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

Test #76:

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

input:

1000
29
355
244
364
795
294
387
548
253
290
405
562
92
119
432
78
361
143
109
440
45
518
44
668
273
69
404
159
149
475
462
443
210
333
49
177
324
58
846
141
330
266
487
320
106
682
120
84
635
40
194
93
235
37
57
10
85
314
661
125
205
1
495
219
412
27
693
62
208
433
349
307
198
229
293
389
173
54
157...

output:

? 989 639
? 358 862
? 375 357
? 743 350
? 589 317
? 406 337
? 403 401
? 41 547
? 539 991
? 249 25
? 592 718
? 631 848
? 820 739
? 574 359
? 305 668
? 103 753
? 301 942
? 917 952
? 126 428
? 160 855
? 423 146
? 232 295
? 346 178
? 648 404
? 699 36
? 261 776
? 366 897
? 844 535
? 472 681
? 590 417
? 7...

result:

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

Test #77:

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

input:

1000
334
412
536
1079
319
272
516
823
1280
383
1135
572
600
337
1346
1974
192
1087
348
827
121
275
779
731
1043
1024
1422
1549
722
110
856
1126
894
125
896
1519
1173
1100
105
243
525
56
504
38
717
1288
1154
37
380
1240
735
147
715
854
89
1035
289
112
1503
196
855
945
369
619
644
1590
1285
1019
19
39...

output:

? 49 46
? 631 141
? 98 402
? 642 692
? 93 720
? 782 954
? 544 514
? 589 807
? 494 783
? 951 243
? 886 85
? 964 719
? 912 321
? 767 390
? 493 700
? 198 221
? 329 580
? 434 386
? 842 72
? 233 107
? 567 655
? 529 182
? 306 414
? 108 854
? 501 663
? 161 551
? 332 473
? 152 749
? 712 336
? 123 345
? 151 ...

result:

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

Test #78:

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

input:

1000
86085
85637
85976
85509
85532
85605
85462
86370
85490
86005
86067
85554
86031
85514
85452
85733
85891
85410
85411
85566
85712
85455
85874
85683
85477
85715
85838
85473
85643
85562
86142
85918
86107
85403
85599
85933
85819
85676
85726
85485
86037
85600
85585
85412
85787
86051
86059
85939
86192
8...

output:

? 463 861
? 658 850
? 585 586
? 505 117
? 183 671
? 854 622
? 993 806
? 438 942
? 57 805
? 539 474
? 982 764
? 54 381
? 885 578
? 595 972
? 901 747
? 42 679
? 234 845
? 40 398
? 905 762
? 720 562
? 212 846
? 227 391
? 517 686
? 880 479
? 169 642
? 630 196
? 707 28
? 366 528
? 611 795
? 162 462
? 648...

result:

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

Test #79:

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

input:

1000
6781
6920
6299
6290
7774
5845
8179
8498
6685
6216
6228
6007
5071
7100
5039
5501
6318
5766
6042
5815
5127
7979
7547
6177
7970
5799
5668
7071
7440
7636
5704
9226
7782
5169
6526
8169
5859
5925
7876
5625
8508
7497
6010
5377
7154
6807
7511
6665
5855
7020
6820
7813
5164
8854
5764
6251
6687
6460
7759
...

output:

? 279 425
? 707 165
? 735 752
? 232 203
? 171 4
? 64 434
? 710 809
? 679 398
? 96 348
? 314 565
? 315 641
? 612 248
? 746 364
? 511 427
? 25 556
? 11 607
? 540 66
? 982 817
? 515 741
? 12 491
? 864 629
? 424 873
? 201 291
? 483 872
? 354 923
? 383 73
? 438 916
? 696 145
? 700 392
? 838 395
? 672 440...

result:

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

Test #80:

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

input:

1000
4068
4973
4110
4556
5613
4192
4116
4241
4871
4551
5367
4724
5208
5258
4729
4213
5720
4914
4455
4336
4273
5660
4244
4896
4351
4882
5394
5552
4075
4614
4186
4884
4089
4052
4209
4056
4853
4797
4230
4286
4111
4320
4284
4220
4883
4124
4113
4206
5584
4057
4783
4661
4942
4837
5497
4262
4794
4060
4745
...

output:

? 90 942
? 927 781
? 528 669
? 414 737
? 666 936
? 129 987
? 713 861
? 64 47
? 787 86
? 417 361
? 26 115
? 382 227
? 475 418
? 629 715
? 721 175
? 411 658
? 630 17
? 866 977
? 876 270
? 398 11
? 2 892
? 72 276
? 827 278
? 951 577
? 369 222
? 976 21
? 350 390
? 330 359
? 30 875
? 917 676
? 24 829
? 8...

result:

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

Test #81:

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

input:

1000
67825
63410
57662
53167
61843
52568
64067
67546
53145
66027
73452
59652
63920
56165
51841
61775
76429
52777
50877
61651
61061
72738
65769
71492
73728
57496
62672
64673
61705
69340
65284
58703
66781
72676
62570
77197
51898
66116
58419
69662
66759
73479
71156
84169
63397
67029
77252
74590
55213
7...

output:

? 117 334
? 33 39
? 676 538
? 195 674
? 667 382
? 487 76
? 352 142
? 426 772
? 949 617
? 964 120
? 697 303
? 427 107
? 601 179
? 266 710
? 95 237
? 155 304
? 157 758
? 900 680
? 806 42
? 271 654
? 207 183
? 287 41
? 767 488
? 793 471
? 365 536
? 920 268
? 974 197
? 818 733
? 378 547
? 261 864
? 215 ...

result:

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

Test #82:

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

input:

1000
105
281
780
627
813
585
670
332
120
140
316
426
411
751
256
171
758
601
93
241
230
90
183
247
17
275
259
136
102
3
347
513
698
41
153
504
563
244
682
242
116
592
305
706
788
34
297
195
206
377
249
488
20
37
1
180
737
274
192
339
52
127
22
543
532
27
29
303
101
46
38
282
8
69
147
873
559
903
549...

output:

? 328 105
? 373 281
? 995 780
? 627 943
? 813 886
? 609 585
? 670 921
? 332 899
? 172 120
? 140 481
? 316 866
? 809 426
? 411 511
? 959 751
? 522 256
? 587 171
? 758 915
? 601 911
? 93 729
? 241 612
? 230 752
? 90 389
? 502 183
? 247 376
? 17 253
? 275 437
? 514 259
? 879 136
? 760 102
? 362 3
? 347...

result:

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

Test #83:

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

input:

1000
46
375
6
356
412
516
191
394
358
521
9
291
197
119
721
401
54
333
28
666
537
15
518
468
143
239
148
43
133
313
806
252
804
315
125
893
443
572
36
635
186
131
355
276
343
208
593
843
118
322
336
347
684
158
260
420
17
583
417
608
179
564
377
437
382
340
25
610
359
108
301
68
159
472
155
295
236
...

output:

? 46 415
? 668 375
? 459 6
? 356 912
? 651 412
? 516 552
? 191 991
? 782 394
? 358 640
? 904 521
? 456 9
? 291 317
? 598 197
? 119 428
? 757 721
? 401 577
? 54 657
? 333 337
? 28 652
? 666 910
? 993 537
? 15 625
? 518 908
? 694 468
? 705 143
? 239 860
? 148 881
? 43 190
? 133 240
? 467 313
? 806 874...

result:

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

Test #84:

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

input:

1000
382
975
24
145
265
612
72
96
516
300
618
337
260
79
98
269
144
254
156
256
35
171
396
761
697
296
859
134
964
656
415
280
551
535
45
733
458
49
361
523
904
562
57
23
94
371
338
16
484
195
259
726
470
233
505
283
258
56
815
584
487
206
548
422
68
325
245
597
330
132
248
80
306
83
201
557
51
170
...

output:

? 846 520
? 797 392
? 203 559
? 881 792
? 254 120
? 872 82
? 488 686
? 602 788
? 780 704
? 80 361
? 160 31
? 235 88
? 772 300
? 5 357
? 133 411
? 312 266
? 323 425
? 513 287
? 724 767
? 601 342
? 655 35
? 285 498
? 163 95
? 74 610
? 509 866
? 533 507
? 540 224
? 682 267
? 466 534
? 274 640
? 525 860...

result:

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

Test #85:

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

input:

1000
443
489
226
655
78
584
440
110
136
352
685
437
39
370
198
335
600
307
215
532
657
723
266
188
269
829
35
449
405
241
763
512
246
898
475
74
122
259
455
92
375
543
804
296
751
230
563
483
111
157
273
267
538
82
13
11
388
102
825
213
446
530
480
417
399
406
3
389
877
98
610
235
323
61
403
137
760...

output:

? 443 663
? 811 489
? 945 226
? 789 655
? 78 670
? 584 641
? 809 440
? 110 216
? 390 136
? 352 368
? 866 685
? 437 827
? 625 39
? 508 370
? 935 198
? 335 764
? 956 600
? 307 689
? 841 215
? 699 532
? 924 657
? 723 759
? 599 266
? 188 598
? 637 269
? 829 848
? 35 116
? 917 449
? 405 911
? 241 901
? 7...

result:

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

Test #86:

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

input:

1000
499
119
371
28
231
379
439
626
10
286
255
518
716
276
383
678
597
746
846
18
445
40
187
45
704
196
550
534
175
611
265
329
433
357
263
727
195
250
72
573
87
757
779
212
481
126
177
191
290
273
498
299
352
6
176
215
51
734
167
565
75
687
25
184
188
254
637
82
340
670
123
209
395
160
595
296
619
...

output:

? 499 984
? 119 450
? 371 876
? 28 169
? 436 231
? 548 379
? 439 979
? 626 855
? 10 732
? 286 898
? 255 363
? 518 653
? 716 878
? 276 475
? 383 697
? 678 982
? 597 817
? 879 746
? 846 867
? 773 18
? 445 856
? 40 502
? 187 991
? 45 530
? 704 842
? 907 196
? 550 800
? 585 534
? 736 175
? 776 611
? 473...

result:

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

Test #87:

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

input:

1000
310
381
727
438
218
691
15
113
123
21
222
577
62
189
433
100
198
715
27
160
545
28
65
353
329
94
924
110
30
666
161
361
283
73
476
301
915
303
152
750
432
70
364
488
12
471
179
639
391
95
366
789
296
539
1
803
262
22
777
234
348
290
109
393
235
81
135
169
143
534
759
525
202
29
403
119
739
293
...

output:

? 310 555
? 909 381
? 727 755
? 438 549
? 218 463
? 691 900
? 69 15
? 782 113
? 123 384
? 586 21
? 417 222
? 606 577
? 62 428
? 189 422
? 433 653
? 487 100
? 684 198
? 943 715
? 27 964
? 160 735
? 545 962
? 56 28
? 65 847
? 353 596
? 865 329
? 94 570
? 924 935
? 110 973
? 30 148
? 829 666
? 870 161
...

result:

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

Subtask #3:

score: 32.6292
Acceptable Answer

Test #88:

score: 32.6292
Acceptable Answer
time: 11ms
memory: 12872kb

input:

1500
482
1431
173
573
562
889
259
134
772
305
703
1048
1283
160
220
423
1097
164
737
195
525
470
57
56
168
33
292
1166
256
274
16
463
184
627
1320
542
127
495
336
24
298
692
720
297
145
241
606
47
342
183
653
275
987
599
1284
8
143
231
1091
608
31
437
501
238
673
773
1367
863
518
6
282
809
171
514
6...

output:

? 1373 482
? 1431 1498
? 173 940
? 1085 573
? 562 801
? 1258 889
? 1177 259
? 134 517
? 797 772
? 1133 305
? 703 922
? 1278 1048
? 1443 1283
? 1376 160
? 220 633
? 423 620
? 1348 1097
? 164 1327
? 1356 737
? 1006 195
? 525 1372
? 470 1023
? 1454 57
? 429 56
? 1410 168
? 1445 33
? 292 696
? 1205 1166...

result:

points 0.40786517550 points  0.40786517550 n = 1500, you used 2750 queries

Test #89:

score: 36.2166
Acceptable Answer
time: 10ms
memory: 12764kb

input:

1500
113
129
1292
1010
517
470
488
1058
373
970
308
1405
267
612
429
199
321
248
80
283
285
949
514
400
1258
101
1132
955
328
210
800
553
183
190
647
264
154
170
627
700
815
592
430
383
349
247
1040
174
97
475
655
257
459
735
854
1012
222
374
193
965
600
614
179
325
393
214
1164
660
269
1230
218
702...

output:

? 1388 1339
? 1372 415
? 137 209
? 446 491
? 984 13
? 1031 944
? 455 1013
? 443 187
? 1128 131
? 531 386
? 1193 194
? 96 18
? 1160 1234
? 889 715
? 1072 133
? 1302 661
? 1044 1180
? 1253 545
? 1119 1421
? 470 1218
? 25 1216
? 552 2
? 987 377
? 815 1101
? 135 243
? 168 1400
? 79 369
? 546 125
? 1173 ...

result:

points 0.45270696520 points  0.45270696520 n = 1500, you used 2427 queries

Test #90:

score: 33.6298
Acceptable Answer
time: 5ms
memory: 12680kb

input:

1500
1168
856
441
261
283
386
503
620
376
342
466
781
354
144
468
123
477
924
707
502
1
420
423
921
300
340
536
879
242
848
131
973
117
101
377
359
607
1054
199
996
668
159
105
733
209
387
308
654
672
271
147
23
514
87
1063
1220
1241
497
425
920
351
1386
394
46
914
252
270
1210
1230
375
559
48
476
6...

output:

? 749 917
? 1073 447
? 221 1230
? 131 1062
? 142 706
? 999 1308
? 252 335
? 1191 325
? 1313 373
? 1163 1330
? 482 1268
? 391 998
? 240 1324
? 109 1429
? 310 1267
? 179 62
? 279 239
? 1039 598
? 354 448
? 830 1250
? 1195 1
? 1291 363
? 393 212
? 931 461
? 1351 351
? 1331 1269
? 1233 818
? 663 440
? 1...

result:

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

Test #91:

score: 33.9899
Acceptable Answer
time: 3ms
memory: 12872kb

input:

1500
980
819
32
481
221
798
630
394
193
1
233
820
688
472
1112
415
180
577
1336
24
143
1452
29
135
544
407
196
511
805
926
117
245
1265
593
547
36
231
999
707
249
615
310
567
333
38
659
382
131
267
821
882
247
698
823
149
185
395
813
1016
483
320
1220
8
102
1127
81
360
322
166
84
733
91
712
203
1357...

output:

? 895 490
? 889 1091
? 16 355
? 1139 1260
? 435 1390
? 743 399
? 315 725
? 629 197
? 268 1404
? 1014 1500
? 288 1384
? 410 930
? 344 764
? 236 1068
? 817 556
? 955 1293
? 90 1261
? 1212 1076
? 715 668
? 12 856
? 940 1429
? 749 726
? 1486 1044
? 698 1433
? 1211 272
? 1297 450
? 1310 98
? 948 1245
? 1...

result:

points 0.42487407860 points  0.42487407860 n = 1500, you used 2616 queries

Test #92:

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

input:

1500
768
195
121
733
360
690
447
621
775
138
167
572
149
631
1043
581
259
1122
270
1331
1015
117
247
299
718
509
5
540
142
1252
227
175
530
1166
1315
692
960
660
293
1392
216
914
178
990
1100
1206
422
851
85
667
278
146
662
358
1026
225
50
1292
340
40
282
133
708
915
267
805
556
208
943
494
705
23
6...

output:

? 206 367
? 302 848
? 1393 811
? 1117 354
? 571 985
? 1455 406
? 349 974
? 1061 369
? 140 1138
? 682 1185
? 316 834
? 438 465
? 825 133
? 1066 199
? 159 1272
? 1041 1289
? 203 880
? 190 20
? 1497 616
? 1416 48
? 1258 1368
? 809 910
? 119 874
? 900 1148
? 1385 392
? 1005 1098
? 753 1147
? 481 1238
? ...

result:

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

Test #93:

score: 33.5673
Acceptable Answer
time: 13ms
memory: 12688kb

input:

1500
1286
462
18
158
298
115
285
102
144
124
1049
421
464
670
727
112
156
46
410
527
969
810
591
288
1275
254
161
489
791
111
274
549
702
663
1155
52
646
501
193
842
483
104
349
1255
473
59
796
593
362
983
629
511
814
1025
302
217
490
35
132
250
281
1038
369
777
704
356
603
191
507
190
114
480
812
2...

output:

? 1393 1442
? 981 465
? 1340 759
? 1127 829
? 899 1053
? 1172 693
? 430 608
? 801 1302
? 822 403
? 348 812
? 226 148
? 1490 540
? 982 79
? 1085 316
? 387 1323
? 65 806
? 828 532
? 773 134
? 955 1284
? 1059 487
? 82 266
? 1168 1155
? 186 455
? 303 894
? 1496 113
? 877 281
? 385 670
? 1403 506
? 355 9...

result:

points 0.41959184260 points  0.41959184260 n = 1500, you used 2656 queries

Test #94:

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

input:

1500
407
100
448
208
632
1031
342
807
551
249
924
93
625
91
244
195
514
722
482
206
740
825
1115
327
408
210
929
912
1024
144
263
429
688
148
98
1200
565
585
603
485
273
36
757
192
469
513
707
1272
1101
84
80
700
718
881
52
58
900
11
974
745
555
22
564
910
132
211
139
229
72
671
402
464
274
268
1053...

output:

? 687 1180
? 54 1301
? 605 83
? 1085 443
? 237 360
? 788 562
? 282 817
? 1082 114
? 144 399
? 1003 35
? 348 1154
? 1074 1315
? 251 1010
? 1300 1319
? 1013 1410
? 1111 495
? 944 473
? 57 1348
? 255 537
? 1089 673
? 328 21
? 150 790
? 730 1388
? 568 847
? 130 685
? 544 1081
? 388 358
? 324 1070
? 1446...

result:

points 0.41373868270 points  0.41373868270 n = 1500, you used 2702 queries

Test #95:

score: 35.5494
Acceptable Answer
time: 3ms
memory: 12864kb

input:

1500
92
186
517
391
535
236
681
74
510
195
292
261
182
134
75
251
311
718
256
111
3
237
320
55
435
600
884
148
88
235
1042
431
448
152
1231
341
615
432
458
46
971
1180
456
460
345
333
641
140
34
429
594
528
956
41
806
465
665
1043
537
107
225
502
305
196
239
669
887
207
1232
722
202
866
536
895
614
...

output:

? 1434 184
? 1395 372
? 373 1034
? 800 782
? 653 1070
? 472 688
? 1362 1468
? 375 148
? 949 1020
? 155 390
? 1150 584
? 522 231
? 364 1445
? 708 268
? 150 541
? 502 1146
? 622 1329
? 493 1436
? 1316 512
? 222 69
? 229 6
? 91 474
? 778 640
? 1237 110
? 1253 870
? 1200 125
? 1213 1233
? 546 296
? 176 ...

result:

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

Test #96:

score: 32.9404
Acceptable Answer
time: 7ms
memory: 12656kb

input:

1500
157
479
689
1037
558
444
893
567
351
753
1412
927
846
392
114
175
28
1302
312
1000
934
590
622
280
177
1289
527
13
459
1426
95
288
338
833
357
717
93
751
796
646
148
376
733
342
669
79
691
723
265
173
1228
456
445
11
250
201
839
984
762
1035
949
31
471
745
420
47
584
1019
268
382
82
52
307
1082...

output:

? 156 778
? 681 478
? 1380 688
? 1036 1336
? 559 719
? 670 445
? 892 1064
? 566 1325
? 350 940
? 752 1496
? 1421 1413
? 1013 926
? 1407 847
? 393 715
? 820 115
? 1399 174
? 760 29
? 1303 1429
? 313 698
? 1001 1046
? 1055 935
? 591 1449
? 1021 623
? 281 1187
? 176 1047
? 1288 1416
? 877 526
? 12 189
...

result:

points 0.41175518280 points  0.41175518280 n = 1500, you used 2718 queries

Test #97:

score: 36.6113
Acceptable Answer
time: 15ms
memory: 12696kb

input:

1500
465
603
233
967
81
903
880
47
109
1036
80
793
84
45
727
993
512
355
123
64
460
545
159
14
120
4
348
116
553
1425
137
862
562
136
522
32
313
565
371
769
61
1321
98
234
558
966
110
238
870
63
176
1095
243
390
482
1083
354
560
1078
380
228
237
8
665
373
11
331
301
368
135
579
755
920
258
150
50
21...

output:

? 430 1037
? 899 222
? 195 1269
? 535 256
? 1421 1207
? 570 599
? 416 620
? 1455 1434
? 1393 507
? 7 464
? 1315 1420
? 4 709
? 1416 1053
? 1457 822
? 775 553
? 509 90
? 988 450
? 597 1147
? 1379 952
? 1436 934
? 293 1040
? 957 340
? 1343 388
? 1486 1045
? 1380 856
? 820 1496
? 1152 1070
? 486 1384
?...

result:

points 0.45764162070 points  0.45764162070 n = 1500, you used 2397 queries

Test #98:

score: 35.7968
Acceptable Answer
time: 3ms
memory: 12856kb

input:

1500
446
338
181
305
197
190
200
1018
435
1395
233
91
625
874
183
210
253
631
1066
934
1340
1105
50
390
666
323
372
13
285
997
45
738
330
62
155
715
243
303
249
59
131
821
641
613
264
113
578
1273
111
620
108
192
898
416
686
994
153
127
621
347
47
600
1164
18
146
201
414
544
322
1381
169
432
791
364...

output:

? 59 276
? 865 1
? 454 597
? 169 3
? 542 808
? 982 756
? 459 1008
? 1011 481
? 625 437
? 1453 1171
? 411 960
? 523 1288
? 1302 75
? 1363 1024
? 386 1371
? 279 1204
? 1155 709
? 932 660
? 1129 117
? 1351 752
? 1475 430
? 799 336
? 17 1472
? 41 954
? 1285 934
? 640 1013
? 198 1003
? 769 378
? 985 1169...

result:

points 0.44746000730 points  0.44746000730 n = 1500, you used 2460 queries

Test #99:

score: 35.6848
Acceptable Answer
time: 10ms
memory: 12876kb

input:

1500
603
1029
1060
464
831
30
722
63
706
400
413
22
487
731
462
1279
50
107
122
34
582
507
589
742
656
593
268
1148
1163
1124
514
678
638
130
189
391
287
226
446
467
822
832
1205
298
657
39
23
477
408
71
281
779
370
156
503
20
476
1015
509
256
438
660
592
318
1177
713
1094
907
55
884
608
1028
84
31
...

output:

? 1412 754
? 1197 1148
? 541 561
? 868 337
? 154 1050
? 570 855
? 147 753
? 4 1301
? 140 905
? 1356 1264
? 634 831
? 1249 230
? 173 979
? 210 939
? 631 1209
? 642 260
? 970 182
? 782 1174
? 1320 986
? 891 322
? 172 699
? 343 534
? 744 1235
? 592 1232
? 1337 240
? 368 630
? 476 874
? 504 1040
? 253 1...

result:

points 0.44606030820 points  0.44606030820 n = 1500, you used 2469 queries

Test #100:

score: 35.4397
Acceptable Answer
time: 0ms
memory: 12928kb

input:

1500
871
512
1065
30
1023
424
300
1149
458
10
1404
503
500
384
188
140
547
675
1199
634
319
764
642
449
29
748
105
173
614
373
784
294
1212
88
49
898
646
271
106
413
924
216
697
147
643
213
909
575
492
1277
1052
312
124
1321
123
322
193
316
120
85
1241
727
343
1075
228
227
46
33
667
60
78
1077
556
1...

output:

? 378 76
? 610 588
? 1487 476
? 110 608
? 946 954
? 1150 125
? 1032 292
? 840 903
? 201 436
? 1173 1317
? 1192 948
? 44 703
? 1164 1272
? 896 564
? 997 584
? 410 1379
? 1145 81
? 414 928
? 1022 508
? 1178 668
? 952 944
? 276 355
? 345 600
? 1104 1174
? 1126 684
? 895 1329
? 994 1442
? 284 30
? 354 5...

result:

points 0.44299585030 points  0.44299585030 n = 1500, you used 2489 queries

Test #101:

score: 32.7935
Acceptable Answer
time: 7ms
memory: 12652kb

input:

1500
1181
370
207
231
2055
323
318
854
63
2240
2133
837
807
1464
232
773
711
1761
1733
2149
1486
302
937
64
1569
1591
1439
399
196
1678
1245
769
2058
162
1162
1110
627
704
1279
1630
541
1209
239
401
2312
542
391
2336
1584
757
1997
358
228
1759
487
410
2276
1496
288
799
2042
2095
786
150
522
1534
152...

output:

? 1161 590
? 1165 180
? 1123 102
? 115 925
? 1330 1023
? 1418 165
? 575 161
? 421 678
? 246 32
? 1118 1237
? 1060 1454
? 1439 412
? 751 394
? 990 734
? 1132 116
? 395 377
? 1492 357
? 881 916
? 989 868
? 1360 1067
? 748 1387
? 613 152
? 1094 460
? 1304 33
? 790 1354
? 1011 799
? 721 1098
? 192 197
?...

result:

points 0.40991917450 points  0.40991917450 n = 1500, you used 2733 queries

Test #102:

score: 32.9109
Acceptable Answer
time: 12ms
memory: 12948kb

input:

1500
85070
85428
85301
85863
86160
85243
85789
84990
85750
85811
84968
85028
85994
85448
85247
85383
85345
85244
85125
85819
85099
85002
84920
86085
85024
85107
85506
86182
85586
85443
86221
84921
84951
85538
85771
86033
85670
85030
85375
84954
85152
85859
85559
85091
85759
85832
85312
85059
85036
8...

output:

? 171 653
? 528 1181
? 401 489
? 963 1139
? 1260 1407
? 344 442
? 978 889
? 91 144
? 1127 850
? 1291 911
? 69 377
? 129 631
? 1094 1208
? 548 1312
? 781 348
? 1298 483
? 1198 445
? 345 389
? 226 1032
? 1246 919
? 215 200
? 103 387
? 21 803
? 1185 1454
? 251 125
? 1314 208
? 606 960
? 1370 1282
? 925...

result:

points 0.41138617890 points  0.41138617890 n = 1500, you used 2721 queries

Test #103:

score: 33.2397
Acceptable Answer
time: 4ms
memory: 12772kb

input:

1500
8683
6241
6254
9917
5855
6350
9044
7388
6586
7084
6982
7616
7909
7061
6419
7936
8813
7617
7012
7324
8014
6583
6257
5273
5166
5230
8250
6510
6400
8753
5436
8831
8429
6057
5239
8039
5911
6039
7013
6811
5405
5737
6459
6699
5198
5466
5602
5261
6043
7708
6477
6207
7458
6836
8134
5080
8958
6101
5654
...

output:

? 1121 1492
? 382 1056
? 1391 387
? 1487 1464
? 1305 260
? 868 421
? 1230 1378
? 1301 737
? 932 500
? 1185 657
? 612 905
? 793 1029
? 895 1021
? 648 718
? 633 443
? 904 1260
? 1159 1390
? 1152 794
? 626 938
? 721 1086
? 1245 927
? 1209 498
? 1081 390
? 92 266
? 47 846
? 303 77
? 1470 1002
? 471 474
...

result:

points 0.4154960250 points  0.4154960250 n = 1500, you used 2688 queries

Test #104:

score: 32.8325
Acceptable Answer
time: 6ms
memory: 12712kb

input:

1500
4125
4678
5563
4192
4740
4648
5445
4706
5590
4731
4031
4929
4145
4369
4962
4266
4986
4213
4243
4179
4822
4747
5044
5331
4781
4599
4536
4454
4146
4312
4209
5195
5412
4464
4252
4725
4889
5317
5561
4292
5126
4969
4621
4524
4668
4436
4967
4357
5128
4415
4265
4294
5584
4133
4759
4221
4719
5326
4396
...

output:

? 1287 97
? 513 1492
? 1164 1408
? 151 531
? 1089 561
? 490 831
? 1078 1255
? 933 537
? 1286 1184
? 872 556
? 25 83
? 1361 693
? 1185 115
? 1157 287
? 722 739
? 1234 209
? 1260 738
? 1463 168
? 190 311
? 140 1494
? 1493 616
? 565 1220
? 898 782
? 1334 999
? 588 628
? 1324 452
? 407 787
? 1132 349
? ...

result:

points 0.41040658360 points  0.41040658360 n = 1500, you used 2729 queries

Test #105:

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

input:

1500
75674
58943
67585
69727
58427
66982
76615
55584
59793
58392
63908
52999
81588
50565
53064
58018
50535
55060
52367
66965
51287
65214
50084
70197
63837
56664
54021
59660
58464
66555
66966
78497
52708
65987
61889
60743
71617
82876
59255
71221
58940
50547
59626
70011
52909
53492
56338
56170
63701
6...

output:

? 1257 1087
? 1331 402
? 1007 753
? 844 1198
? 377 808
? 1371 729
? 1123 1475
? 258 1226
? 434 497
? 450 374
? 1005 599
? 411 148
? 1323 1364
? 1159 35
? 149 1300
? 1275 357
? 33 95
? 236 600
? 115 1317
? 1429 727
? 69 736
? 658 1009
? 425 5
? 1250 867
? 764 595
? 312 314
? 707 192
? 716 430
? 1154 ...

result:

points 0.41411352670 points  0.41411352670 n = 1500, you used 2699 queries

Test #106:

score: 36.518
Acceptable Answer
time: 8ms
memory: 12668kb

input:

1500
380
1047
248
793
670
477
151
231
460
508
1189
317
1019
260
1171
395
1301
313
1351
434
713
708
296
374
398
222
455
300
47
121
553
181
61
663
242
499
359
496
1296
86
484
759
890
272
36
989
372
172
212
649
905
888
502
756
291
447
385
730
368
797
332
379
348
672
1140
1167
904
678
130
1060
205
1326
...

output:

? 1231 14
? 1020 350
? 1245 1375
? 549 964
? 1194 1129
? 284 85
? 655 271
? 975 579
? 405 467
? 730 1276
? 228 1156
? 1363 793
? 1080 544
? 959 321
? 1256 864
? 779 241
? 1137 581
? 1010 1012
? 432 153
? 668 224
? 1371 1356
? 12 1051
? 282 999
? 1428 1321
? 1374 279
? 855 686
? 307 1410
? 543 805
? ...

result:

points 0.45647559590 points  0.45647559590 n = 1500, you used 2404 queries

Test #107:

score: 35.9098
Acceptable Answer
time: 4ms
memory: 12768kb

input:

1500
1107
1738
639
571
169
589
1382
791
977
979
929
30
1152
1109
376
1007
990
137
155
591
750
947
1648
203
102
693
1195
99
511
54
544
943
171
65
440
1166
200
1537
290
664
709
1602
586
573
934
572
989
983
1288
437
80
864
17
616
95
296
394
512
782
842
202
1657
271
863
1408
1977
122
489
56
295
193
1065...

output:

? 974 898
? 1319 649
? 1390 777
? 1281 767
? 870 29
? 1324 1228
? 580 616
? 41 563
? 1089 1160
? 585 165
? 329 995
? 372 936
? 535 566
? 419 252
? 390 1257
? 1355 302
? 384 161
? 1075 807
? 619 27
? 1495 242
? 255 933
? 1082 1493
? 1112 43
? 451 741
? 539 520
? 474 48
? 564 413
? 339 139
? 1124 197
...

result:

points 0.44887289060 points  0.44887289060 n = 1500, you used 2451 queries

Test #108:

score: 36.2295
Acceptable Answer
time: 3ms
memory: 12648kb

input:

1500
84910
85705
85244
84903
84901
86068
85112
85356
85914
85567
85446
85022
85306
84965
85108
85074
85743
85114
85281
84973
85132
85184
85288
85665
85472
86207
85166
85266
85149
85329
84919
85046
85083
85680
85807
85226
85668
84908
86018
85170
86131
85385
85235
85107
86016
85457
84917
85289
84968
8...

output:

? 1328 1500
? 1046 1028
? 80 1407
? 300 1220
? 879 1276
? 532 593
? 1448 1197
? 271 1199
? 1246 648
? 902 454
? 328 350
? 260 1497
? 553 978
? 784 889
? 1447 778
? 446 1312
? 672 533
? 583 702
? 362 787
? 638 297
? 1087 105
? 402 249
? 332 435
? 1137 1231
? 575 217
? 890 1134
? 1125 1461
? 1330 481
...

result:

points 0.45286886480 points  0.45286886480 n = 1500, you used 2426 queries

Test #109:

score: 35.6848
Acceptable Answer
time: 7ms
memory: 12924kb

input:

1500
6005
7667
8071
7930
5295
6069
6279
5556
5933
5651
6071
6707
8546
7331
6502
5180
6969
7224
7117
6653
6558
5162
9115
5820
6848
5288
6280
5018
5091
5047
7226
8618
5762
6845
5121
5372
5909
5919
7606
8466
7807
7493
6115
6105
7519
5868
5623
5721
5688
8323
5005
8767
5603
6621
5364
6144
5489
5377
8581
...

output:

? 623 591
? 834 632
? 1310 1048
? 1070 1375
? 725 1191
? 865 1307
? 24 152
? 174 889
? 321 1353
? 245 499
? 597 268
? 871 1239
? 1448 1031
? 1119 711
? 1185 1334
? 456 71
? 857 810
? 832 864
? 521 288
? 616 742
? 394 962
? 279 173
? 196 322
? 179 1053
? 1386 839
? 770 72
? 586 720
? 947 1401
? 1061 ...

result:

points 0.44606030820 points  0.44606030820 n = 1500, you used 2469 queries

Test #110:

score: 37.4278
Acceptable Answer
time: 0ms
memory: 12864kb

input:

1500
4480
4516
4986
4173
4663
4586
4050
4260
5294
4049
4533
4433
5225
4058
4772
4131
5249
4837
4103
5022
4064
4288
4521
4550
4185
4272
4543
4268
4640
4312
4670
4808
4375
5432
5005
4174
4122
4598
4932
5423
5525
5016
4046
4365
4068
4537
4999
4922
5455
4679
4000
4817
5243
5784
4175
4069
4542
4965
4818
...

output:

? 779 25
? 92 670
? 1347 955
? 604 239
? 7 673
? 970 1103
? 1101 1114
? 581 821
? 204 1486
? 738 899
? 880 824
? 1126 1298
? 603 1273
? 1104 40
? 375 60
? 1295 1302
? 618 526
? 1429 828
? 726 273
? 219 140
? 1436 883
? 720 1016
? 98 234
? 528 181
? 1085 760
? 532 823
? 1156 1002
? 1053 1193
? 680 10...

result:

points 0.46784728490 points  0.46784728490 n = 1500, you used 2338 queries

Test #111:

score: 35.3671
Acceptable Answer
time: 3ms
memory: 12644kb

input:

1500
68611
52423
50676
78619
75055
54730
62390
51166
67458
50867
52974
51115
56477
59670
53448
57728
56423
57829
64110
64810
55739
63466
71619
63030
61417
60709
85095
65739
75548
67711
73083
75677
55014
53796
65705
65104
68793
65749
51477
66594
66352
83743
64875
77443
53167
51532
62355
54285
51632
6...

output:

? 439 915
? 1468 1456
? 270 1015
? 106 124
? 7 329
? 1487 587
? 603 561
? 1240 215
? 1401 371
? 548 998
? 1090 269
? 1250 103
? 1500 1176
? 725 364
? 551 780
? 536 933
? 1092 822
? 343 584
? 1103 1458
? 893 37
? 54 1194
? 365 385
? 294 402
? 146 887
? 14 377
? 200 1306
? 134 890
? 581 988
? 104 945
...

result:

points 0.44208858940 points  0.44208858940 n = 1500, you used 2495 queries

Test #112:

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

input:

1500
1076
613
919
116
593
347
216
1290
241
943
612
984
696
374
1348
172
209
220
491
87
299
306
558
376
713
545
373
573
175
1003
152
455
2
503
349
54
1426
1047
1272
435
69
702
171
336
377
161
948
917
133
1106
147
416
534
779
592
93
345
1260
994
33
461
423
62
208
46
245
620
178
1432
490
385
158
128
11...

output:

? 1076 1278
? 613 1110
? 1005 919
? 727 116
? 1489 593
? 347 1470
? 216 1455
? 1290 1441
? 1425 241
? 943 1405
? 764 612
? 1293 984
? 1120 696
? 374 1375
? 1391 1348
? 172 1173
? 807 209
? 220 1436
? 491 1153
? 329 87
? 299 1025
? 306 356
? 558 1035
? 376 424
? 1305 713
? 772 545
? 373 972
? 832 573...

result:

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

Test #113:

score: 33.8935
Acceptable Answer
time: 5ms
memory: 12696kb

input:

1500
438
806
287
234
394
366
575
818
67
551
211
1059
1125
618
453
682
420
1252
621
530
462
184
922
908
599
249
947
8
556
82
1079
614
318
1300
620
778
334
181
792
673
307
777
877
300
998
572
638
528
525
1315
200
451
429
672
97
301
94
1087
3
687
72
897
508
127
764
133
516
291
549
759
207
1164
594
177
...

output:

? 438 1188
? 806 950
? 1099 287
? 234 323
? 394 1100
? 366 945
? 575 678
? 1173 818
? 552 67
? 1373 551
? 695 211
? 1059 1250
? 1125 1214
? 991 618
? 936 453
? 682 845
? 679 420
? 1267 1252
? 1032 621
? 530 674
? 462 1410
? 1482 184
? 922 1350
? 1466 908
? 755 599
? 249 401
? 1049 947
? 8 1200
? 556...

result:

points 0.42366925280 points  0.42366925280 n = 1500, you used 2625 queries

Test #114:

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

input:

1500
12
868
1211
487
42
219
64
834
256
602
231
565
205
1170
88
1120
515
435
1033
1164
679
108
1145
291
483
27
667
55
637
365
752
421
824
69
129
469
351
21
164
228
10
187
156
684
697
920
152
265
423
180
836
329
892
266
407
250
362
309
122
304
990
595
247
262
35
912
722
273
323
893
213
434
29
1102
121...

output:

? 650 494
? 428 1451
? 838 1315
? 1253 1442
? 88 1378
? 1495 1430
? 1373 403
? 342 51
? 1428 410
? 787 1391
? 364 938
? 1027 783
? 737 729
? 712 907
? 1278 1452
? 579 447
? 596 232
? 599 1246
? 251 551
? 620 803
? 1337 1286
? 885 1449
? 333 855
? 1478 1131
? 10 439
? 239 434
? 427 183
? 210 932
? 86...

result:

points 0.4480863130 points  0.4480863130 n = 1500, you used 2456 queries

Test #115:

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

input:

1500
48
436
403
681
94
1149
407
322
102
527
294
234
580
58
282
179
104
129
621
456
4
478
930
450
42
532
173
1107
326
529
816
34
1292
1189
819
183
533
1032
137
8
411
77
1301
854
722
1227
391
300
385
549
642
71
1010
683
128
75
80
76
302
11
1269
626
434
159
1143
396
703
613
619
830
425
513
395
291
213
...

output:

? 48 273
? 436 651
? 403 900
? 691 681
? 1056 94
? 1272 1149
? 911 407
? 322 891
? 1114 102
? 527 1167
? 294 414
? 794 234
? 580 1059
? 58 936
? 1339 282
? 179 1342
? 199 104
? 1014 129
? 621 779
? 1376 456
? 494 4
? 478 669
? 930 1190
? 656 450
? 59 42
? 532 1055
? 173 317
? 1422 1107
? 326 1064
? ...

result:

points 0.41187838610 points  0.41187838610 n = 1500, you used 2717 queries

Test #116:

score: 34.5175
Acceptable Answer
time: 7ms
memory: 12636kb

input:

1500
213
859
21
39
499
122
407
670
434
733
475
540
362
1492
441
58
95
720
865
358
107
235
251
782
403
455
1039
396
118
1157
1096
241
196
851
35
93
351
385
710
129
321
319
226
218
178
142
205
1136
225
731
393
356
574
104
891
380
135
257
79
460
354
170
215
907
975
451
560
292
830
102
513
355
487
82
48...

output:

? 786 213
? 859 1085
? 21 1371
? 39 868
? 1425 499
? 963 122
? 1460 407
? 670 906
? 434 1353
? 869 733
? 475 793
? 1050 540
? 362 549
? 1500 1492
? 1307 441
? 924 58
? 95 1054
? 784 720
? 865 1362
? 1370 358
? 107 1275
? 235 666
? 251 566
? 1435 782
? 403 1182
? 455 1153
? 1039 1293
? 396 1324
? 147...

result:

points 0.43146854710 points  0.43146854710 n = 1500, you used 2568 queries

Test #117:

score: 34.8594
Acceptable Answer
time: 0ms
memory: 12776kb

input:

1500
670
85
707
585
995
834
752
68
81
293
527
53
264
1189
146
76
246
682
239
349
400
180
6
521
1304
558
221
971
1054
491
83
256
626
232
422
5
1224
40
1000
305
772
28
871
392
972
736
195
934
171
332
1104
251
72
587
511
63
391
272
1130
357
549
634
379
285
69
466
188
962
441
365
23
892
19
363
281
197
1...

output:

? 670 1303
? 85 1181
? 1166 707
? 672 585
? 995 1306
? 1393 834
? 822 752
? 1382 68
? 81 235
? 293 696
? 527 1074
? 53 348
? 264 1202
? 1189 1249
? 757 146
? 76 531
? 275 246
? 1425 682
? 239 1445
? 1047 349
? 693 400
? 180 1230
? 1409 6
? 935 521
? 1304 1407
? 1394 558
? 1279 221
? 971 1321
? 1365 ...

result:

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