QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765718#8267. Staring Contest_8_8_#52.084946 21ms12944kbC++204.2kb2024-11-20 15:04:482024-11-20 15:04:48

Judging History

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

  • [2024-11-20 15:04:48]
  • 评测
  • 测评结果:52.084946
  • 用时:21ms
  • 内存:12944kb
  • [2024-11-20 15:04:48]
  • 提交

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(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: 12508kb

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

input:

2
1

output:

? 2 1
! 1 1 

result:

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

Test #3:

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

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: 4ms
memory: 12516kb

input:

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

output:

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

result:

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

Test #5:

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

input:

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

output:

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

result:

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

Test #6:

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

input:

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

output:

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

result:

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

Test #7:

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

input:

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

output:

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

result:

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

Test #8:

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

input:

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

output:

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

result:

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

Test #9:

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

input:

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

output:

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

result:

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

Test #10:

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

input:

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

output:

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

result:

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

Test #11:

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

input:

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

output:

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

result:

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

Test #12:

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

input:

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

output:

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

result:

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

Test #13:

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

input:

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

output:

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

result:

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

Test #14:

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

input:

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

output:

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

result:

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

Test #15:

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

input:

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

output:

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

result:

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

Test #16:

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

input:

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

output:

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

result:

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

Test #17:

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

input:

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

output:

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

result:

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

Test #18:

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

input:

50
86364
86356
86390
86378
86369
86360
86366
86367
86379
86365
86357
86350
86372
86361
86380
86355
86374
86394
86370
86353
86358
86352
86351
86375
86363
86363
86385
86354
86362
86353
86370
86393
86374
86359
86389
86394
86398
86383
86357
86384
86392
86376
86366
86360
86386
86378
86390
86356
86364
863...

output:

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

result:

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

Test #19:

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

input:

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

output:

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

result:

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

Test #20:

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

input:

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

output:

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

result:

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

Test #21:

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

input:

50
67638
52391
67289
54556
56991
52428
73709
78428
58109
50918
66090
61154
70891
60767
69824
54962
62431
72805
52604
51290
56134
65062
70252
53250
50293
50293
70252
65062
56134
57154
52604
75191
62431
54962
69824
60767
75191
61154
66090
50918
58109
75191
82221
52428
57364
54556
74688
52391
67638
843...

output:

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

result:

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

Test #22:

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

input:

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

output:

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

result:

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

Test #23:

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

input:

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

output:

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

result:

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

Test #24:

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

input:

50
86364
86350
86361
86369
86367
86351
86358
86378
86357
86359
86374
86355
86389
86384
86354
86388
86363
86353
86362
86373
86386
86381
86365
86360
86352
86366
86365
86366
86381
86386
86380
86353
86371
86388
86354
86392
86390
86355
86374
86359
86357
86378
86390
86390
86375
86369
86390
86350
86364
863...

output:

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

result:

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

Test #25:

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

input:

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

output:

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

result:

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

Test #26:

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

input:

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

output:

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

result:

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

Test #27:

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

input:

50
58717
67069
54250
70928
70576
53987
62990
62248
80286
61401
76671
57318
66448
53213
68422
67005
58357
75023
65477
72585
51658
54630
61968
55504
53454
55504
61968
54630
51658
72620
65477
74083
76101
76101
68422
72291
76101
76101
76101
76671
78154
75075
72987
67146
71272
70928
80286
67069
77213
712...

output:

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

result:

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

Test #28:

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

input:

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

output:

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

result:

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

Test #29:

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

input:

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

output:

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

result:

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

Test #30:

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

input:

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

output:

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

result:

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

Test #31:

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

input:

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

output:

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

result:

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

Test #32:

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

input:

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

output:

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

result:

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

Test #33:

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

input:

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

output:

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

result:

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

Test #34:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #35:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #36:

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

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

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

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

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #39:

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

input:

4
2
5
2
3

output:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #41:

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

input:

4
5
2
2
3

output:

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

result:

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

Test #42:

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

input:

4
5
2
3
3

output:

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

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: 0ms
memory: 12564kb

input:

4
2
5
2
3

output:

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

result:

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

Test #45:

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

input:

4
3
2
2
3
5

output:

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

input:

4
2
3
2
3
5

output:

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

input:

4
2
3
5

output:

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

result:

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

Test #48:

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

input:

4
2
3
5

output:

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

result:

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

Test #49:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #50:

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

input:

4
2
3
5

output:

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

result:

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

Test #51:

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

input:

4
5
2
3

output:

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

result:

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

Test #52:

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

input:

4
3
2
3
2
5

output:

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

input:

4
5
2
2
3

output:

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

input:

4
5
2
2
3
3

output:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #56:

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

input:

4
5
2
2
3

output:

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

result:

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

Test #57:

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

input:

4
5
2
2
3

output:

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

result:

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

Subtask #2:

score: 11
Accepted

Test #58:

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

input:

1000
23
98
325
337
180
38
379
447
384
123
282
276
415
104
105
85
292
623
100
683
429
876
224
216
548
183
553
472
713
707
314
53
327
27
356
9
645
64
275
18
701
378
291
90
550
102
29
266
25
459
400
518
297
238
485
218
262
89
139
342
75
207
561
424
259
783
355
214
126
855
228
132
128
118
283
185
55
274...

output:

? 718 23
? 265 98
? 325 382
? 337 393
? 843 180
? 38 316
? 379 567
? 447 734
? 384 824
? 427 123
? 465 282
? 276 827
? 884 415
? 835 104
? 223 105
? 268 85
? 292 394
? 865 623
? 100 284
? 749 683
? 429 450
? 876 972
? 224 939
? 216 766
? 548 908
? 702 183
? 581 553
? 472 653
? 926 713
? 707 778
? 57...

result:

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

Test #59:

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

input:

1000
291
47
397
71
72
368
658
554
218
596
260
462
24
1
223
62
574
27
64
214
209
45
498
691
68
531
479
357
81
382
49
592
206
599
250
449
74
475
510
497
61
182
141
80
90
300
815
661
446
146
124
177
466
425
26
622
14
514
343
127
37
73
453
637
404
450
452
434
455
731
46
861
780
52
325
75
138
284
258
233...

output:

? 710 466
? 529 954
? 363 604
? 479 930
? 929 159
? 184 633
? 343 299
? 197 447
? 783 436
? 405 403
? 651 741
? 482 539
? 977 827
? 1000 897
? 778 759
? 939 853
? 124 427
? 974 544
? 641 937
? 354 787
? 792 101
? 175 956
? 169 503
? 310 98
? 273 933
? 470 62
? 8 522
? 394 644
? 831 920
? 328 619
? 9...

result:

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

Test #60:

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

input:

1000
66
175
760
224
84
863
488
136
537
255
359
174
822
409
105
62
390
220
420
638
275
596
726
528
269
699
45
21
348
167
238
410
10
403
489
179
258
616
17
93
28
277
57
738
140
530
56
112
803
24
72
613
435
82
204
134
48
467
901
769
264
206
724
237
130
244
561
619
219
423
624
153
647
13
330
612
365
655...

output:

? 968 684
? 88 812
? 532 621
? 889 229
? 519 959
? 512 432
? 757 635
? 933 405
? 571 269
? 255 128
? 303 180
? 914 391
? 539 590
? 373 205
? 199 53
? 970 755
? 253 806
? 891 616
? 791 464
? 437 682
? 138 325
? 435 703
? 458 638
? 737 698
? 135 292
? 350 583
? 23 381
? 131 11
? 827 276
? 903 84
? 605...

result:

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

Test #61:

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

input:

1000
545
770
124
301
39
704
514
182
603
651
566
297
478
245
368
502
364
470
921
355
398
101
565
203
357
183
417
197
3
650
293
380
247
849
674
248
252
98
59
40
698
336
667
421
681
472
93
463
45
584
453
238
46
623
167
105
139
274
237
551
746
216
848
61
951
569
854
4
340
452
165
712
876
491
655
8
374
5...

output:

? 403 728
? 482 385
? 62 936
? 850 817
? 981 333
? 352 494
? 257 514
? 91 399
? 536 699
? 621 675
? 283 506
? 611 852
? 282 239
? 878 447
? 388 184
? 251 509
? 489 182
? 537 235
? 477 540
? 823 819
? 407 199
? 933 950
? 718 622
? 899 773
? 822 387
? 909 221
? 792 738
? 902 591
? 999 727
? 412 325
? ...

result:

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

Test #62:

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

input:

1000
265
502
309
414
753
566
440
494
793
134
544
464
217
514
266
216
238
431
203
935
951
509
212
211
417
630
399
657
643
568
51
190
247
482
260
294
315
308
407
521
145
99
705
362
525
501
380
423
244
791
858
473
478
489
165
434
179
458
181
64
32
359
163
828
470
503
579
187
398
695
48
23
498
80
872
30...

output:

? 14 633
? 856 250
? 882 655
? 264 294
? 912 877
? 218 131
? 863 281
? 254 855
? 897 33
? 801 434
? 165 229
? 269 227
? 609 77
? 244 1
? 850 368
? 303 393
? 382 100
? 793 716
? 602 740
? 968 10
? 8 976
? 755 771
? 310 395
? 79 606
? 709 23
? 905 186
? 789 700
? 829 111
? 154 822
? 73 217
? 526 821
?...

result:

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

Test #63:

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

input:

1000
422
606
232
873
493
326
234
86
445
134
557
132
83
19
216
108
218
420
467
96
849
812
144
506
20
520
2
51
747
124
183
126
276
11
370
173
54
61
531
262
112
605
244
759
191
773
372
18
401
334
429
31
34
193
25
116
722
724
142
194
169
482
75
361
133
699
91
189
650
105
28
73
147
880
714
483
625
323
51...

output:

? 771 711
? 99 803
? 184 616
? 64 44
? 254 784
? 161 663
? 617 782
? 912 543
? 278 793
? 71 567
? 222 874
? 780 566
? 641 459
? 661 491
? 608 192
? 554 411
? 655 609
? 885 710
? 267 231
? 548 615
? 74 76
? 30 906
? 840 572
? 753 764
? 510 119
? 165 760
? 501 659
? 540 475
? 96 127
? 562 381
? 409 32...

result:

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

Test #64:

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

input:

1000
334
341
177
217
311
135
712
509
110
95
75
43
31
181
86
297
462
393
523
152
392
383
17
184
220
354
567
751
145
252
10
223
140
838
15
292
441
365
56
169
851
210
703
76
639
168
206
178
748
681
21
172
256
57
11
483
574
366
584
585
918
198
167
492
26
9
897
399
467
648
530
396
537
382
105
745
25
20
8...

output:

? 333 692
? 522 319
? 194 647
? 316 567
? 379 598
? 618 731
? 424 852
? 932 18
? 59 781
? 811 395
? 851 500
? 915 109
? 219 939
? 313 639
? 829 922
? 182 407
? 936 77
? 294 215
? 192 46
? 614 697
? 181 217
? 780 235
? 967 935
? 353 633
? 259 561
? 293 110
? 134 270
? 864 502
? 681 711
? 497 365
? 98...

result:

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

Test #65:

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

input:

1000
409
312
184
385
382
25
702
740
258
749
420
169
354
50
63
262
202
296
278
147
26
579
486
251
14
114
316
665
937
235
622
388
456
61
411
192
250
564
452
183
378
40
687
467
95
199
212
615
383
237
159
146
505
656
6
725
504
47
96
327
447
270
448
599
666
304
9
187
52
742
478
195
450
469
406
110
221
13...

output:

? 818 785
? 624 229
? 509 368
? 875 770
? 553 764
? 293 50
? 597 79
? 133 521
? 824 516
? 357 503
? 867 840
? 338 898
? 945 708
? 720 100
? 126 865
? 524 457
? 908 404
? 592 143
? 556 888
? 718 294
? 52 913
? 843 567
? 223 972
? 737 502
? 28 140
? 228 775
? 173 632
? 671 55
? 127 99
? 470 895
? 757 ...

result:

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

Test #66:

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

input:

1000
587
38
99
555
386
483
187
107
610
220
575
589
297
265
272
171
28
559
954
579
576
690
394
240
208
338
582
282
211
490
197
221
704
252
52
424
874
176
92
270
280
144
385
275
87
264
448
373
70
232
466
701
459
49
16
130
283
330
484
310
508
299
558
695
668
156
116
151
180
872
182
132
77
533
200
124
3...

output:

? 586 969
? 39 269
? 692 98
? 554 847
? 443 387
? 812 482
? 255 186
? 106 715
? 991 611
? 520 221
? 627 574
? 588 814
? 296 549
? 668 264
? 741 273
? 841 170
? 344 29
? 558 831
? 956 955
? 912 578
? 577 623
? 946 691
? 791 395
? 478 241
? 209 364
? 339 932
? 982 583
? 826 283
? 762 210
? 491 830
? 1...

result:

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

Test #67:

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

input:

1000
770
169
452
83
622
184
429
867
110
607
752
497
146
248
443
294
391
390
933
221
268
38
743
446
329
231
522
72
299
399
347
515
111
729
636
46
9
588
91
747
547
495
289
450
214
47
334
182
379
673
627
422
216
241
188
120
102
509
61
44
756
584
571
207
344
814
253
36
385
176
638
161
899
75
625
368
172...

output:

? 230 147
? 833 419
? 548 497
? 919 288
? 378 295
? 399 816
? 573 531
? 100 135
? 718 890
? 77 395
? 248 94
? 88 505
? 247 854
? 102 752
? 559 499
? 706 547
? 535 611
? 610 593
? 69 64
? 781 217
? 14 732
? 948 962
? 47 259
? 554 134
? 400 673
? 771 571
? 20 478
? 224 928
? 703 123
? 107 603
? 243 65...

result:

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

Test #68:

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

input:

300
158
189
40
23
277
196
14
25
154
122
42
38
9
68
29
18
20
258
1
56
74
246
80
51
35
17
133
66
113
130
108
65
124
43
191
2
45
3
72
216
127
278
138
185
4
39
52
63
99
59
190
11
187
60
36
75
37
267
142
31
199
95
222
157
114
69
16
94
91
174
93
67
228
129
163
101
161
173
27
19
7
118
197
33
116
106
182
12...

output:

? 291 158
? 262 189
? 268 40
? 23 32
? 287 277
? 196 247
? 214 14
? 25 194
? 294 154
? 144 122
? 193 42
? 38 96
? 86 9
? 77 68
? 238 29
? 266 18
? 20 224
? 298 258
? 1 107
? 273 56
? 74 283
? 246 292
? 235 80
? 51 229
? 62 35
? 17 55
? 133 261
? 66 170
? 113 236
? 130 269
? 151 108
? 263 65
? 124 27...

result:

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

Test #69:

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

input:

300
194
179
171
36
41
54
211
111
103
143
131
229
169
202
74
96
58
34
155
9
39
122
186
23
157
66
21
95
30
31
206
14
37
129
94
87
40
82
33
61
224
6
57
252
60
25
52
32
193
153
217
102
26
59
243
139
3
121
10
49
17
70
43
79
68
249
2
260
38
64
181
1
69
51
42
50
256
56
100
105
253
77
15
142
24
20
7
47
172
...

output:

? 189 299
? 209 106
? 19 24
? 133 44
? 134 179
? 18 47
? 241 62
? 72 203
? 197 66
? 283 117
? 190 36
? 65 15
? 3 230
? 48 182
? 229 123
? 144 40
? 210 89
? 204 242
? 171 143
? 86 257
? 6 23
? 92 132
? 275 261
? 139 98
? 259 216
? 136 192
? 63 165
? 50 234
? 188 110
? 255 146
? 224 8
? 64 202
? 12 79...

result:

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

Test #70:

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

input:

1000
256
155
115
654
161
507
798
848
192
356
2
655
140
258
676
957
30
66
166
318
516
74
33
5
193
589
448
568
285
224
277
505
252
515
367
509
116
459
261
387
402
281
302
185
123
370
134
300
283
262
460
13
49
831
512
376
92
555
152
94
296
576
160
90
53
110
404
55
260
101
141
112
93
607
264
179
409
114...

output:

? 832 522
? 393 236
? 875 21
? 320 410
? 536 624
? 774 651
? 980 525
? 665 865
? 65 920
? 56 801
? 748 376
? 306 907
? 979 474
? 549 40
? 997 814
? 588 860
? 571 368
? 448 566
? 206 216
? 457 231
? 836 662
? 883 81
? 17 389
? 407 765
? 963 429
? 398 881
? 617 148
? 858 585
? 547 246
? 119 974
? 441 ...

result:

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

Test #71:

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

input:

1000
1627
638
129
1232
877
470
675
828
260
1127
1462
18
1499
217
1239
33
1907
799
1373
1077
955
1766
607
199
287
490
945
733
62
331
745
528
734
41
482
1281
577
606
1212
1835
1814
19
153
534
952
874
71
11
477
1117
1252
111
8
165
1743
344
1454
294
1243
427
1645
223
521
374
612
24
819
82
755
829
683
19...

output:

? 821 834
? 333 800
? 263 72
? 757 629
? 836 452
? 611 246
? 669 352
? 427 936
? 138 985
? 880 582
? 939 746
? 12 887
? 765 998
? 114 194
? 634 853
? 24 970
? 989 949
? 663 413
? 721 697
? 555 875
? 750 491
? 924 877
? 317 498
? 101 250
? 275 150
? 967 257
? 485 626
? 379 401
? 38 775
? 172 979
? 95...

result:

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

Test #72:

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

input:

1000
85476
85735
85621
85567
85819
85474
85935
86076
85778
86170
85570
86010
85607
85663
86046
85814
85702
85591
86313
85555
85542
85498
86029
85997
86204
85558
86094
85517
86352
85415
85418
86021
85801
85650
85933
85761
85780
85477
85535
85537
85550
85485
85770
86124
85642
85678
86233
85703
86306
8...

output:

? 77 958
? 336 588
? 718 222
? 168 922
? 937 420
? 178 75
? 535 536
? 676 761
? 379 600
? 770 999
? 606 171
? 610 637
? 208 359
? 783 264
? 646 942
? 641 415
? 487 303
? 452 192
? 945 913
? 880 156
? 451 143
? 697 99
? 629 731
? 597 643
? 846 804
? 935 159
? 694 695
? 118 169
? 956 952
? 16 566
? 71...

result:

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

Test #73:

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

input:

1000
7431
5410
6311
6053
6821
6243
7990
6288
6362
7657
6823
5022
7820
7026
5710
6465
5323
5543
5026
5182
7115
6100
6067
5942
7409
5914
6659
7336
7066
5815
5844
5304
8493
6689
6048
5544
7343
6700
6008
7718
5750
5560
8619
7030
5762
7965
5239
5031
5201
7207
6173
5385
7483
5736
7348
8669
6429
6194
8502
...

output:

? 448 829
? 126 65
? 339 227
? 304 186
? 939 330
? 218 491
? 645 570
? 327 224
? 238 293
? 505 589
? 900 331
? 5 205
? 540 717
? 789 373
? 659 122
? 262 727
? 54 242
? 749 89
? 6 599
? 26 58
? 395 499
? 259 198
? 189 573
? 162 412
? 669 444
? 157 975
? 289 347
? 429 781
? 416 385
? 137 553
? 365 140...

result:

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

Test #74:

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

input:

1000
5023
4262
4486
5146
4155
5314
4236
4896
4838
4058
5239
4776
5617
4259
4805
4855
4650
4564
4857
4843
4900
4514
4264
4117
5102
4142
4525
4079
5175
4723
4645
4123
4966
5806
4035
4619
4707
4897
4300
5267
4086
4018
4094
5111
5282
4276
4231
4884
4594
4100
4065
4986
4220
5318
4977
4257
5255
5600
4483
...

output:

? 865 509
? 943 142
? 871 247
? 885 575
? 857 88
? 784 660
? 214 126
? 448 614
? 727 419
? 164 27
? 621 827
? 456 389
? 953 807
? 141 830
? 401 995
? 428 667
? 324 867
? 277 578
? 873 429
? 422 515
? 451 611
? 513 260
? 143 297
? 285 59
? 831 548
? 127 78
? 541 265
? 36 155
? 593 998
? 996 363
? 658...

result:

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

Test #75:

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

input:

1000
65598
58700
72747
60475
67973
50653
51338
67491
55880
57392
57262
56773
67490
65431
59255
58643
56157
62474
64577
75005
63964
62567
72591
69890
58047
67919
51278
64087
51199
74326
61897
54080
54159
66654
66603
58382
75636
56946
76436
54398
74632
60775
73707
51952
66903
50566
72841
57069
69992
5...

output:

? 514 417
? 233 320
? 766 631
? 275 620
? 491 703
? 13 528
? 32 558
? 937 478
? 142 850
? 749 197
? 394 190
? 402 178
? 477 983
? 411 633
? 526 246
? 682 232
? 661 151
? 502 327
? 386 401
? 700 974
? 919 365
? 927 333
? 778 626
? 617 541
? 946 219
? 571 489
? 289 31
? 372 480
? 871 29
? 673 948
? 31...

result:

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

Test #76:

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

input:

1000
581
329
138
34
283
603
691
766
22
311
388
458
241
610
614
116
751
83
352
488
235
20
630
206
155
358
181
269
126
288
429
401
141
6
259
10
8
219
410
397
74
571
146
832
594
865
56
565
499
231
2
340
854
152
333
151
19
218
67
224
119
511
207
545
318
115
580
72
427
830
604
609
891
466
748
519
733
188...

output:

? 809 701
? 861 773
? 353 554
? 583 365
? 609 685
? 502 18
? 874 892
? 2 819
? 231 29
? 172 454
? 974 347
? 37 607
? 968 498
? 340 921
? 250 426
? 316 898
? 112 235
? 804 379
? 30 142
? 718 467
? 842 729
? 888 993
? 705 748
? 927 755
? 437 732
? 286 310
? 469 855
? 725 331
? 72 536
? 456 228
? 873 1...

result:

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

Test #77:

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

input:

1000
1248
182
282
49
1421
548
1547
222
1231
862
1316
1344
318
78
1376
642
68
88
813
493
958
1240
241
632
203
844
112
706
56
1306
93
775
60
650
481
279
667
334
826
779
1466
233
655
729
823
200
46
617
335
373
1479
190
1576
75
463
639
637
1206
1099
24
18
280
219
248
153
1038
1363
1460
1167
586
1124
296...

output:

? 208 162
? 579 959
? 742 937
? 281 917
? 680 82
? 619 823
? 31 669
? 572 908
? 472 744
? 320 501
? 853 890
? 1 488
? 164 454
? 460 39
? 473 570
? 329 192
? 342 77
? 436 144
? 809 335
? 650 179
? 797 212
? 150 305
? 30 222
? 265 552
? 675 654
? 646 326
? 983 706
? 998 448
? 755 591
? 470 425
? 507 3...

result:

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

Test #78:

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

input:

1000
85729
86020
85718
85822
85610
85457
85574
85882
85957
86262
85992
85559
85526
85732
85501
85702
85430
85848
85958
85763
85746
86008
85955
85797
85528
85976
85644
85950
85517
85867
86240
85883
86329
86221
85549
86013
85684
85586
85750
86001
86077
85723
85424
85657
85435
85906
85817
85428
85631
8...

output:

? 583 436
? 602 613
? 353 904
? 677 400
? 256 500
? 395 973
? 999 700
? 682 539
? 358 592
? 902 217
? 698 57
? 849 227
? 675 21
? 728 627
? 585 435
? 229 81
? 671 822
? 554 420
? 601 978
? 27 68
? 426 19
? 412 319
? 345 963
? 280 295
? 994 143
? 134 586
? 553 160
? 306 450
? 485 506
? 285 78
? 393 3...

result:

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

Test #79:

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

input:

1000
8677
5431
5827
5249
5428
7412
5501
8766
9358
6717
6336
8235
5815
9311
5495
8094
6585
5530
5909
6457
6775
6473
6206
5030
7444
7284
7100
6042
5266
7491
5135
5077
8914
5461
6607
5941
5635
6963
9842
7894
5490
5671
6887
5060
7511
5496
5563
7572
5672
5272
6254
6569
6251
7013
6280
7233
7785
6614
5753
...

output:

? 475 86
? 404 262
? 451 75
? 733 261
? 688 581
? 660 564
? 503 11
? 479 711
? 407 535
? 267 655
? 31 709
? 579 601
? 942 12
? 663 417
? 677 127
? 87 132
? 118 914
? 968 659
? 690 170
? 91 773
? 917 297
? 328 949
? 223 148
? 322 613
? 443 883
? 814 675
? 511 58
? 741 473
? 632 874
? 847 652
? 534 95...

result:

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

Test #80:

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

input:

1000
5587
5040
4348
4345
5002
4456
4477
4252
5121
5875
5310
5637
4653
5451
4111
4300
4413
5659
5151
4170
4745
4167
4115
4448
5184
4444
5387
4082
5564
4641
4479
4388
5056
5430
4731
4462
4426
5262
4884
4410
5171
4154
4391
4631
5516
5536
4712
5280
5369
4370
4113
4451
5217
4676
5261
4333
4080
5059
4212
...

output:

? 702 332
? 641 127
? 757 762
? 756 632
? 215 730
? 294 539
? 818 862
? 536 609
? 190 156
? 46 259
? 196 380
? 544 497
? 906 765
? 855 59
? 232 556
? 866 583
? 631 549
? 613 330
? 172 327
? 442 257
? 677 176
? 701 734
? 494 360
? 264 301
? 416 558
? 312 917
? 720 830
? 182 896
? 510 288
? 505 371
? ...

result:

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

Test #81:

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

input:

1000
50536
60114
81735
55502
84286
63250
55373
50216
53465
55255
57573
63905
50293
60076
50521
55860
58512
59652
69334
73728
51368
57662
71781
73005
66804
55654
58771
77837
57353
55105
75244
68963
50053
60073
62647
58110
57770
55634
82311
51166
64673
71299
64649
53553
82133
57581
54483
52281
60307
6...

output:

? 392 72
? 296 413
? 109 672
? 861 492
? 9 995
? 994 550
? 429 356
? 904 353
? 186 583
? 598 998
? 503 718
? 666 616
? 82 663
? 346 168
? 924 559
? 92 249
? 328 963
? 183 107
? 154 908
? 536 808
? 878 164
? 538 477
? 253 857
? 424 522
? 465 482
? 419 57
? 686 651
? 106 80
? 661 282
? 441 84
? 36 888...

result:

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

Test #82:

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

input:

1000
991
336
144
425
327
13
579
293
238
215
116
605
405
593
567
557
131
82
41
878
583
47
56
343
443
624
71
721
402
473
278
434
411
7
527
305
799
760
32
627
496
234
302
88
286
69
112
261
216
340
270
24
202
14
108
224
254
68
15
440
839
772
257
685
435
767
100
153
231
67
581
154
639
398
686
175
146
185...

output:

? 991 993
? 844 336
? 420 144
? 425 669
? 942 327
? 13 589
? 579 854
? 293 552
? 238 424
? 215 850
? 116 162
? 621 605
? 654 405
? 593 653
? 567 948
? 759 557
? 131 586
? 82 824
? 41 927
? 973 878
? 583 990
? 47 622
? 56 284
? 343 939
? 688 443
? 624 782
? 937 71
? 721 786
? 402 768
? 473 753
? 899 ...

result:

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

Test #83:

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

input:

1000
580
55
112
517
86
172
521
292
213
104
285
52
548
85
407
581
272
756
372
44
329
184
465
40
114
279
83
354
153
132
475
322
93
327
126
530
332
443
99
552
485
563
718
20
863
254
291
145
127
421
15
201
342
575
265
32
478
223
216
585
401
107
366
69
808
10
210
615
640
546
541
58
117
707
786
227
218
11...

output:

? 977 580
? 339 55
? 112 897
? 517 556
? 352 86
? 172 807
? 695 521
? 846 292
? 213 666
? 823 104
? 285 901
? 52 636
? 663 548
? 553 85
? 578 407
? 583 581
? 439 272
? 756 876
? 372 709
? 44 730
? 670 329
? 434 184
? 633 465
? 40 626
? 315 114
? 279 393
? 83 298
? 618 354
? 392 153
? 534 132
? 503 4...

result:

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

Test #84:

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

input:

1000
860
291
59
260
107
340
114
557
522
153
868
619
261
138
2
391
68
600
4
841
71
86
49
881
203
254
157
21
35
281
124
771
564
295
185
361
412
390
90
19
413
613
586
995
182
344
530
82
382
234
268
569
293
131
116
256
265
305
247
133
651
546
352
141
347
180
158
354
191
263
50
54
631
140
15
403
768
466
...

output:

? 661 149
? 372 936
? 715 385
? 772 599
? 867 628
? 337 141
? 699 714
? 755 643
? 445 301
? 298 681
? 912 773
? 595 512
? 802 862
? 344 689
? 925 275
? 835 818
? 675 487
? 807 189
? 100 676
? 527 609
? 928 951
? 614 371
? 935 117
? 561 538
? 437 584
? 829 287
? 585 116
? 156 574
? 490 35
? 40 264
? ...

result:

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

Test #85:

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

input:

1000
113
480
92
174
42
112
184
685
400
132
143
43
458
829
140
27
550
247
612
344
135
356
114
501
198
245
96
297
333
207
61
887
518
444
226
425
396
94
505
433
180
724
497
9
388
541
792
263
221
596
341
476
597
37
82
504
20
800
406
250
429
439
494
224
367
555
723
54
289
38
127
868
275
540
241
50
166
1
...

output:

? 251 113
? 690 480
? 92 165
? 794 174
? 211 42
? 112 811
? 184 268
? 820 685
? 423 400
? 132 873
? 143 689
? 43 427
? 537 458
? 829 989
? 140 817
? 257 27
? 633 550
? 609 247
? 612 737
? 646 344
? 575 135
? 588 356
? 375 114
? 501 626
? 445 198
? 705 245
? 661 96
? 805 297
? 333 644
? 207 702
? 181...

result:

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

Test #86:

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

input:

1000
479
188
17
22
88
565
513
753
267
19
246
298
191
891
391
693
291
350
14
114
414
511
749
434
568
218
64
639
625
92
79
77
703
98
386
82
477
36
335
196
892
228
363
35
173
21
234
129
340
732
777
445
119
274
755
349
377
637
440
163
593
604
561
314
682
67
324
299
353
206
436
76
506
204
341
632
54
343
...

output:

? 479 734
? 468 188
? 187 17
? 22 333
? 707 88
? 613 565
? 580 513
? 806 753
? 267 894
? 841 19
? 246 602
? 397 298
? 261 191
? 891 959
? 391 862
? 693 990
? 611 291
? 350 761
? 14 950
? 114 121
? 935 414
? 609 511
? 749 820
? 879 434
? 568 975
? 218 986
? 533 64
? 639 824
? 625 883
? 523 92
? 79 79...

result:

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

Test #87:

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

input:

1000
520
161
115
65
362
632
290
448
200
406
132
507
194
276
205
828
299
82
96
324
703
275
75
215
501
226
576
526
5
416
101
227
17
9
225
282
14
698
259
237
548
24
102
544
35
61
556
123
210
10
148
445
83
374
373
49
248
311
734
337
141
125
391
313
211
523
104
387
552
192
500
885
68
55
325
303
217
163
1...

output:

? 610 520
? 161 771
? 494 115
? 923 65
? 362 612
? 632 741
? 290 882
? 448 925
? 596 200
? 406 737
? 993 132
? 507 606
? 194 627
? 276 571
? 693 205
? 828 949
? 482 299
? 976 82
? 96 910
? 324 720
? 703 953
? 297 275
? 385 75
? 215 572
? 501 749
? 226 254
? 576 583
? 643 526
? 5 383
? 546 416
? 253 ...

result:

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

Subtask #3:

score: 32.0849
Acceptable Answer

Test #88:

score: 33.6821
Acceptable Answer
time: 7ms
memory: 12944kb

input:

1500
127
249
520
1025
232
34
1106
1137
174
726
1322
376
728
112
935
55
766
442
237
372
219
1067
923
74
878
702
303
571
390
539
1162
267
132
668
139
644
616
1310
490
905
1297
775
529
156
779
126
60
380
315
62
308
47
671
574
44
27
250
1118
151
1230
171
339
541
465
359
82
410
389
540
402
489
1186
473
4...

output:

? 127 785
? 1072 249
? 520 881
? 1025 1454
? 1073 232
? 1038 34
? 1106 1271
? 1402 1137
? 637 174
? 849 726
? 1474 1322
? 1270 376
? 1251 728
? 112 813
? 935 1350
? 55 1426
? 873 766
? 442 778
? 237 1033
? 372 706
? 1500 219
? 1071 1067
? 1334 923
? 74 612
? 1448 878
? 702 1180
? 751 303
? 571 1312
...

result:

points 0.42102601260 points  0.42102601260 n = 1500, you used 2645 queries

Test #89:

score: 38.6476
Acceptable Answer
time: 5ms
memory: 12876kb

input:

1500
132
94
1212
595
518
136
443
175
599
272
160
1149
186
212
434
892
488
73
508
300
604
730
693
22
1196
340
305
245
540
279
1122
977
576
1097
492
49
993
405
48
367
179
584
360
975
163
430
860
896
1422
539
933
613
265
641
598
240
687
848
494
330
68
969
1077
463
11
50
491
34
191
119
1191
429
166
155
...

output:

? 1369 616
? 1407 57
? 22 289
? 906 460
? 862 983
? 498 1365
? 1058 344
? 1197 1326
? 902 714
? 1229 1145
? 1341 1090
? 352 36
? 1315 677
? 1205 1289
? 1067 736
? 609 398
? 1013 378
? 1101 1428
? 993 64
? 1201 90
? 897 76
? 55 771
? 808 297
? 1308 1479
? 305 13
? 391 1161
? 1196 707
? 1256 1037
? 64...

result:

points 0.4830955120 points  0.4830955120 n = 1500, you used 2257 queries

Test #90:

score: 35.0929
Acceptable Answer
time: 11ms
memory: 12816kb

input:

1500
308
297
377
712
541
519
304
522
856
705
514
553
363
310
215
138
10
1293
620
431
1108
232
442
707
781
438
948
277
173
266
344
538
741
966
27
213
190
713
55
524
437
263
640
583
200
79
571
687
100
563
337
300
731
407
602
503
299
205
562
1109
57
392
807
879
390
1124
214
23
655
691
686
778
556
287
9...

output:

? 1135 1347
? 149 166
? 189 601
? 571 1145
? 271 628
? 620 260
? 809 1349
? 904 1240
? 1073 995
? 576 353
? 1118 1244
? 574 277
? 182 1065
? 1089 1346
? 817 108
? 1432 239
? 1496 52
? 647 737
? 852 1191
? 274 216
? 947 662
? 1385 395
? 796 1280
? 354 655
? 391 1075
? 1282 1030
? 845 1027
? 1195 139
...

result:

points 0.43866072040 points  0.43866072040 n = 1500, you used 2518 queries

Test #91:

score: 35.1519
Acceptable Answer
time: 8ms
memory: 12628kb

input:

1500
715
723
240
392
51
1310
739
388
640
609
138
61
503
523
451
192
406
1298
502
36
350
482
664
337
1191
248
81
849
143
575
21
782
911
747
257
870
327
262
680
1012
452
712
1248
18
791
972
1415
187
169
125
161
701
1242
402
682
722
1108
875
1037
315
249
878
236
407
1355
167
749
518
355
1057
372
71
341...

output:

? 637 1143
? 575 1139
? 120 158
? 196 405
? 1451 1475
? 779 655
? 410 1131
? 1217 194
? 320 360
? 1196 471
? 69 616
? 985 1470
? 641 1249
? 1178 1239
? 831 1275
? 1041 96
? 1082 203
? 649 753
? 251 970
? 18 1283
? 1120 175
? 241 423
? 661 332
? 450 1332
? 698 905
? 124 1259
? 1460 571
? 999 1076
? 6...

result:

points 0.43939927440 points  0.43939927440 n = 1500, you used 2513 queries

Test #92:

score: 35.9225
Acceptable Answer
time: 6ms
memory: 12696kb

input:

1500
570
1178
298
585
461
879
56
287
1176
1213
198
545
178
282
676
399
79
176
429
1151
221
962
820
149
11
666
124
222
43
473
1037
437
152
1207
502
362
537
51
1251
2
237
313
716
686
525
743
1256
350
450
518
1069
1125
830
182
107
762
888
732
490
520
618
976
351
19
774
339
815
185
230
1325
1155
483
853...

output:

? 241 466
? 162 15
? 229 602
? 1043 434
? 981 394
? 256 1190
? 342 723
? 1365 894
? 163 1392
? 1492 1357
? 1080 652
? 1406 1023
? 662 237
? 610 356
? 413 293
? 117 950
? 790 482
? 1417 663
? 965 75
? 1326 1475
? 352 861
? 270 1493
? 341 1498
? 825 483
? 756 898
? 418 112
? 1204 689
? 640 154
? 461 7...

result:

points 0.44903070230 points  0.44903070230 n = 1500, you used 2450 queries

Test #93:

score: 35.8595
Acceptable Answer
time: 6ms
memory: 12756kb

input:

1500
774
482
338
293
96
15
873
510
60
682
82
43
147
929
535
602
859
370
709
959
883
703
353
699
462
1097
698
26
373
340
958
835
458
435
303
246
135
73
1002
742
665
187
732
116
1096
1095
1154
283
339
105
821
1063
627
372
430
215
1482
393
511
746
454
592
1321
25
374
360
937
199
37
1004
163
33
289
165
...

output:

? 1137 1349
? 1122 991
? 919 546
? 152 604
? 798 99
? 345 743
? 139 314
? 1005 175
? 720 780
? 1260 1091
? 1107 791
? 729 482
? 677 238
? 1418 286
? 1420 483
? 1051 1052
? 321 1493
? 935 506
? 55 396
? 271 1470
? 309 1204
? 399 1417
? 1472 574
? 66 401
? 981 1257
? 1403 202
? 1099 1241
? 1306 763
? ...

result:

points 0.44824329890 points  0.44824329890 n = 1500, you used 2455 queries

Test #94:

score: 32.0849
Acceptable Answer
time: 5ms
memory: 12708kb

input:

1500
1216
357
1181
922
373
587
286
236
176
331
156
143
821
158
118
1156
831
866
270
903
96
1104
600
374
1003
945
248
1084
1434
207
1151
1232
690
1168
598
273
206
320
783
28
111
832
1068
229
134
995
239
472
91
661
37
68
495
645
562
522
210
92
24
624
820
157
375
753
43
775
715
125
265
1037
530
439
684...

output:

? 938 932
? 227 787
? 862 1130
? 374 344
? 737 755
? 327 16
? 577 929
? 114 1029
? 177 1149
? 839 424
? 1189 587
? 1215 610
? 1066 142
? 1185 1032
? 1265 1067
? 1020 812
? 1334 162
? 232 1308
? 961 1074
? 346 306
? 969 1309
? 708 1330
? 301 440
? 1116 753
? 506 972
? 436 390
? 475 1005
? 1064 668
? ...

result:

points 0.40106182020 points  0.40106182020 n = 1500, you used 2808 queries

Test #95:

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

input:

1500
219
231
617
281
97
367
559
295
140
192
96
449
516
563
123
165
897
129
89
90
407
485
727
717
34
93
977
229
274
271
793
570
380
883
501
421
900
590
685
715
85
69
351
385
376
352
525
1093
543
110
1258
810
80
505
362
184
998
588
108
811
50
603
254
13
60
386
1019
482
378
58
828
735
187
277
11
653
56...

output:

? 438 1163
? 462 713
? 1234 1236
? 605 562
? 1079 194
? 3 734
? 1298 1118
? 1316 590
? 280 877
? 1237 384
? 474 192
? 898 1330
? 1032 1146
? 1126 1356
? 1455 246
? 803 330
? 49 1207
? 258 494
? 178 853
? 180 488
? 1245 814
? 970 1449
? 223 1454
? 429 1434
? 68 673
? 287 186
? 885 1047
? 458 1458
? 5...

result:

points 0.48408955140 points  0.48408955140 n = 1500, you used 2252 queries

Test #96:

score: 32.9503
Acceptable Answer
time: 11ms
memory: 12768kb

input:

1500
940
6
392
1020
1021
1102
777
153
37
1464
667
223
72
177
750
155
529
43
263
464
894
365
767
46
2
451
709
41
28
343
189
560
804
663
251
8
338
596
479
506
406
1074
491
1095
194
191
195
237
608
483
851
221
877
213
657
98
492
138
482
640
122
821
666
927
74
758
428
304
769
1259
569
496
447
123
786
20...

output:

? 1248 941
? 7 395
? 393 542
? 1021 1214
? 1020 1031
? 1103 1186
? 993 776
? 469 152
? 36 1304
? 1498 1465
? 666 764
? 1216 222
? 73 1342
? 176 729
? 890 751
? 154 170
? 1223 528
? 79 42
? 406 262
? 604 465
? 895 1486
? 965 364
? 838 766
? 47 93
? 1208 3
? 450 730
? 708 958
? 537 40
? 57 29
? 1107 3...

result:

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

Test #97:

score: 38.9364
Acceptable Answer
time: 18ms
memory: 12920kb

input:

1500
241
769
17
843
637
34
133
285
1163
260
388
500
1097
823
672
596
625
555
309
236
576
200
575
152
593
559
718
329
266
273
662
569
226
1131
31
23
48
815
425
599
228
644
305
77
184
265
1305
998
180
598
377
27
742
1101
1015
943
302
7
1099
123
677
607
549
694
1300
857
43
164
1409
106
91
119
281
303
1...

output:

? 1261 858
? 733 207
? 1246 1485
? 534 659
? 638 865
? 1036 1466
? 1369 35
? 1217 266
? 330 339
? 719 1240
? 1112 1050
? 1000 121
? 349 405
? 679 425
? 828 3
? 601 904
? 877 862
? 947 613
? 1005 1193
? 444 1264
? 924 125
? 979 1300
? 927 908
? 986 1348
? 909 359
? 943 274
? 674 782
? 1173 830
? 467 ...

result:

points 0.48670531190 points  0.48670531190 n = 1500, you used 2239 queries

Test #98:

score: 37.4708
Acceptable Answer
time: 12ms
memory: 12688kb

input:

1500
10
128
95
464
698
382
1073
72
319
1206
451
763
455
1022
1151
37
1306
378
40
180
677
1403
415
1146
799
126
199
706
325
750
15
509
439
964
151
462
195
253
115
59
100
639
231
354
667
155
659
1103
822
517
213
544
1210
389
238
255
532
598
730
412
773
432
856
103
87
422
655
1068
956
27
156
620
218
81...

output:

? 1339 1270
? 821 974
? 927 687
? 234 392
? 231 493
? 43 1242
? 717 308
? 1150 907
? 1168 97
? 955 685
? 945 814
? 155 196
? 869 1104
? 1015 1059
? 944 182
? 243 563
? 1032 1020
? 619 1180
? 158 1407
? 46 1039
? 376 108
? 1365 1450
? 127 157
? 322 321
? 980 775
? 632 1219
? 1338 991
? 790 820
? 1449...

result:

points 0.46838524130 points  0.46838524130 n = 1500, you used 2335 queries

Test #99:

score: 36.8546
Acceptable Answer
time: 7ms
memory: 12916kb

input:

1500
427
960
215
312
207
11
409
746
334
458
48
54
2
190
76
425
6
791
221
105
381
537
497
195
1070
650
576
904
636
284
403
1031
81
462
769
1022
647
211
254
648
303
1127
64
308
269
538
188
317
144
981
60
229
93
637
939
495
186
845
655
982
412
97
355
1237
106
1057
283
128
123
432
65
1202
820
71
294
267...

output:

? 103 335
? 963 789
? 394 1433
? 561 706
? 1104 1382
? 36 1169
? 381 1025
? 80 700
? 612 1386
? 916 2
? 83 211
? 357 218
? 578 237
? 1395 1240
? 1181 1269
? 52 800
? 1051 1100
? 352 692
? 455 429
? 569 1026
? 877 106
? 595 909
? 722 1473
? 167 746
? 460 209
? 619 482
? 1083 1272
? 202 273
? 609 1273...

result:

points 0.46068226530 points  0.46068226530 n = 1500, you used 2379 queries

Test #100:

score: 35.4518
Acceptable Answer
time: 21ms
memory: 12700kb

input:

1500
111
1118
739
636
433
288
827
30
71
99
649
460
85
668
91
552
203
1002
87
462
794
721
98
1077
76
399
753
7
496
109
495
458
170
834
576
526
1420
846
286
8
530
192
468
763
146
1115
540
132
228
291
1057
1427
285
954
201
941
317
384
4
454
962
356
1346
635
835
559
472
663
200
489
341
65
609
385
110
39...

output:

? 916 792
? 630 1035
? 460 729
? 604 1433
? 874 394
? 678 1304
? 536 368
? 110 43
? 465 1391
? 986 963
? 22 132
? 1417 180
? 791 55
? 486 251
? 1144 738
? 703 852
? 1016 119
? 1360 319
? 1142 913
? 1154 1324
? 886 547
? 1124 341
? 704 281
? 1099 440
? 312 1332
? 680 1268
? 476 21
? 248 330
? 13 498
...

result:

points 0.44314759530 points  0.44314759530 n = 1500, you used 2488 queries

Test #101:

score: 33.6821
Acceptable Answer
time: 13ms
memory: 12684kb

input:

1500
924
1076
983
1764
650
1164
1390
1735
709
1169
660
1775
169
962
607
566
2660
1872
1281
1262
2
2378
1874
1196
1757
1245
475
1280
675
1180
2637
982
272
883
336
1100
692
391
380
580
876
93
1312
1605
658
1566
1824
868
1411
444
1853
1306
473
545
2171
626
259
627
1546
1645
843
2220
293
1507
400
1279
2...

output:

? 455 732
? 629 537
? 1488 486
? 1089 883
? 317 1467
? 583 1462
? 1466 694
? 1383 869
? 1054 355
? 1312 586
? 856 323
? 889 1203
? 799 86
? 1389 472
? 299 408
? 738 279
? 1333 1447
? 1094 938
? 964 641
? 630 1161
? 2 902
? 1238 1190
? 1043 939
? 597 1224
? 879 1195
? 622 924
? 1166 237
? 1126 640
? ...

result:

points 0.42102601260 points  0.42102601260 n = 1500, you used 2645 queries

Test #102:

score: 33.8085
Acceptable Answer
time: 5ms
memory: 12816kb

input:

1500
85463
85558
85922
84943
85801
85431
85002
85140
85873
85126
85395
84986
85283
85507
84939
85539
86104
85150
85323
85100
85411
85751
85698
85373
85231
85516
85061
85033
85662
85254
85414
86015
85495
84956
85641
85577
85351
84942
85046
85078
85462
85876
85741
85137
85303
84934
85192
85763
84937
8...

output:

? 563 1018
? 658 731
? 1303 1022
? 168 44
? 1005 901
? 531 674
? 992 103
? 241 457
? 991 973
? 227 532
? 495 987
? 87 813
? 384 1463
? 607 1458
? 40 1117
? 639 1276
? 1204 1367
? 251 998
? 835 423
? 297 201
? 511 1180
? 1233 851
? 1134 798
? 473 1041
? 1120 332
? 1366 616
? 162 259
? 1281 134
? 1240...

result:

points 0.42260636080 points  0.42260636080 n = 1500, you used 2633 queries

Test #103:

score: 33.8191
Acceptable Answer
time: 7ms
memory: 12880kb

input:

1500
5822
6255
5210
6702
7040
9206
6238
6012
6287
5002
6069
6011
5627
6223
6416
8266
5981
8346
8109
7466
5295
6189
7710
5856
5336
7784
6254
5489
6896
6140
6507
5840
6344
5265
5267
8979
8483
6739
6264
5787
8551
5484
8954
7803
5396
5824
5610
5040
6699
5202
5544
5583
5926
5955
5691
8646
6705
6678
5193
...

output:

? 633 249
? 388 805
? 67 1094
? 713 533
? 638 1392
? 1391 1270
? 1380 379
? 1410 311
? 1240 397
? 1230 1
? 1327 324
? 1438 310
? 1004 194
? 375 1303
? 442 1185
? 1008 1258
? 300 1224
? 1172 1032
? 1116 961
? 1135 756
? 381 103
? 1370 363
? 1193 832
? 705 261
? 848 113
? 1274 855
? 924 387
? 155 889
...

result:

points 0.42273881120 points  0.42273881120 n = 1500, you used 2632 queries

Test #104:

score: 33.7557
Acceptable Answer
time: 10ms
memory: 12868kb

input:

1500
4145
4251
4602
4052
4937
4439
5016
5515
4329
4262
4217
4166
4216
4550
5157
5198
4384
4679
4207
4197
4824
4138
4733
5197
4009
4896
5786
4355
4720
5598
5423
4193
5257
4915
4199
4352
5412
5208
4107
5021
5547
5199
4245
4968
4806
4147
4667
4132
4608
4670
4133
4206
5462
4893
4191
4755
4514
4538
5000
...

output:

? 527 115
? 197 769
? 1292 455
? 1277 43
? 777 699
? 652 337
? 1020 763
? 1130 1178
? 1474 256
? 1419 205
? 622 172
? 131 1432
? 315 171
? 1476 418
? 1433 875
? 906 1298
? 1001 298
? 514 1007
? 1466 163
? 154 1338
? 618 767
? 723 108
? 633 557
? 1185 905
? 339 7
? 667 812
? 1477 1332
? 1269 277
? 54...

result:

points 0.42194585780 points  0.42194585780 n = 1500, you used 2638 queries

Test #105:

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

input:

1500
70597
78037
61409
69804
53932
76780
71472
58133
58183
51844
56672
50255
66309
67585
66174
66858
51344
53291
63354
52673
56323
52786
53889
50280
78270
53122
54195
51516
74253
53651
63952
64401
83084
70795
68854
58314
54571
68389
70463
55651
56871
72298
56588
61043
81665
54805
50547
63208
50785
6...

output:

? 1262 889
? 1475 1180
? 495 1400
? 849 1357
? 189 933
? 1138 1291
? 1363 928
? 362 1033
? 366 1376
? 797 93
? 314 568
? 304 12
? 703 1223
? 804 753
? 1306 695
? 903 726
? 74 447
? 162 1100
? 798 567
? 128 891
? 1161 293
? 133 1436
? 185 1093
? 842 17
? 1189 1441
? 1115 151
? 578 201
? 590 83
? 1113...

result:

points 0.41765799550 points  0.41765799550 n = 1500, you used 2671 queries

Test #106:

score: 35.3189
Acceptable Answer
time: 6ms
memory: 12912kb

input:

1500
14
193
523
802
32
558
97
200
186
729
840
150
533
397
1290
334
257
623
146
100
128
584
169
277
1019
608
222
610
577
279
996
431
40
822
202
376
37
130
854
678
1085
767
708
45
571
709
57
652
224
223
86
617
1128
248
843
1354
176
689
48
385
454
887
13
229
158
926
63
76
8
696
43
195
2
776
356
337
357...

output:

? 694 512
? 298 716
? 1428 814
? 1354 1475
? 164 1412
? 648 1364
? 925 352
? 258 178
? 58 146
? 592 162
? 1078 924
? 1255 963
? 1368 107
? 322 873
? 1332 312
? 1225 1335
? 411 904
? 1399 344
? 891 1209
? 128 735
? 271 27
? 546 779
? 773 206
? 292 317
? 149 1080
? 1445 1089
? 855 315
? 307 672
? 808 ...

result:

points 0.44148678320 points  0.44148678320 n = 1500, you used 2499 queries

Test #107:

score: 34.6986
Acceptable Answer
time: 8ms
memory: 12880kb

input:

1500
547
28
1220
14
119
996
218
406
864
26
721
670
1899
849
203
785
689
477
485
284
445
211
442
1357
930
1507
283
1167
1791
890
453
35
37
793
30
113
167
1140
757
1268
277
756
1619
1814
1007
297
1305
549
22
328
131
54
991
535
164
830
222
322
55
1625
1795
999
1324
713
738
84
570
98
230
92
1672
205
916...

output:

? 991 259
? 813 1015
? 990 201
? 1233 671
? 658 454
? 703 1256
? 1225 788
? 261 33
? 1332 404
? 1110 821
? 1497 2
? 771 135
? 845 1419
? 455 851
? 451 533
? 941 1353
? 617 1457
? 542 1420
? 904 612
? 785 342
? 152 1482
? 1202 284
? 590 1217
? 294 1190
? 398 601
? 450 1486
? 100 934
? 145 1005
? 486 ...

result:

points 0.4337327410 points  0.4337327410 n = 1500, you used 2552 queries

Test #108:

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

input:

1500
85225
85082
85384
86116
85044
85145
84947
85449
85932
85312
84928
85589
85073
85479
84902
86026
85380
85026
85694
85473
85014
85378
85332
85275
85064
85027
85663
85623
84998
85142
85043
85523
85297
84943
85591
85889
84935
85094
85802
84929
84953
85537
85115
85065
85633
84984
85035
85636
85534
8...

output:

? 785 100
? 920 636
? 997 1056
? 217 789
? 1374 388
? 935 974
? 441 1132
? 1191 660
? 384 1079
? 12 1481
? 704 151
? 1059 1431
? 921 1110
? 308 455
? 1354 1299
? 874 159
? 1207 626
? 679 212
? 557 534
? 344 1064
? 232 277
? 80 733
? 587 751
? 1214 370
? 1309 1281
? 313 42
? 742 1210
? 1039 484
? 743...

result:

points 0.43821932730 points  0.43821932730 n = 1500, you used 2521 queries

Test #109:

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

input:

1500
5515
8598
7331
6416
7111
7100
5295
6184
5066
6222
5192
8764
5919
6686
6213
6381
6324
6653
8278
5834
5251
5692
6298
6414
6310
5289
5549
6009
6818
5494
7162
5816
8574
7321
7221
5203
6623
8392
7034
7455
6069
7363
9038
6722
6833
7444
5429
5734
5603
8582
6618
5854
5489
6228
6524
8417
7811
9523
6058
...

output:

? 1141 1189
? 761 1476
? 1119 1112
? 1245 1036
? 941 1278
? 1387 574
? 1191 328
? 1383 177
? 1089 796
? 1301 507
? 1444 589
? 129 81
? 1047 1336
? 605 1363
? 1360 1236
? 602 683
? 226 62
? 616 849
? 1324 1397
? 1475 995
? 1341 1123
? 1300 1315
? 1237 1208
? 15 550
? 336 953
? 999 358
? 718 937
? 713...

result:

points 0.4495051360 points  0.4495051360 n = 1500, you used 2447 queries

Test #110:

score: 36.5713
Acceptable Answer
time: 9ms
memory: 12744kb

input:

1500
4140
4622
4355
4091
5171
4087
4807
4183
4069
4738
5326
4047
4046
4858
4643
4882
4099
4061
5365
5594
4618
4935
4486
4615
4271
4685
4391
4313
5591
4772
4516
4493
4936
4561
4869
4145
4690
4478
4550
5062
5064
4878
4750
4306
4009
4031
4932
4571
4687
4528
4393
4378
4990
4645
4194
4678
4084
4361
5114
...

output:

? 1397 105
? 1040 674
? 1356 148
? 1154 320
? 1460 446
? 732 663
? 838 292
? 28 994
? 336 874
? 471 376
? 651 766
? 733 332
? 630 1043
? 95 1206
? 725 594
? 310 1194
? 1112 1395
? 1145 434
? 346 872
? 822 297
? 140 14
? 495 298
? 1304 1118
? 1317 293
? 507 617
? 121 156
? 774 942
? 97 1265
? 992 786...

result:

points 0.45714078550 points  0.45714078550 n = 1500, you used 2400 queries

Test #111:

score: 35.6724
Acceptable Answer
time: 17ms
memory: 12636kb

input:

1500
57923
55514
61473
67669
59128
61589
60403
51770
68228
60917
53285
66911
55546
51675
82450
55937
52318
57045
73592
65709
60002
53044
59278
54644
51632
50023
68961
55571
50037
54756
65947
82922
52834
63475
50450
52973
56468
60439
56020
55198
62107
55014
56670
55245
56017
65139
67072
68158
54535
6...

output:

? 1331 692
? 3 600
? 1356 783
? 888 797
? 856 366
? 468 205
? 20 511
? 1210 1494
? 1067 552
? 184 864
? 1373 1421
? 847 1149
? 1243 1241
? 328 519
? 1252 368
? 1045 1077
? 603 1330
? 826 374
? 90 1271
? 1397 1257
? 391 994
? 94 487
? 924 426
? 1024 472
? 1418 1137
? 93 1014
? 481 249
? 1155 662
? 12...

result:

points 0.44590558930 points  0.44590558930 n = 1500, you used 2470 queries

Test #112:

score: 38.5058
Acceptable Answer
time: 5ms
memory: 12908kb

input:

1500
593
697
359
217
183
1126
1285
244
972
376
1
32
18
289
486
751
821
160
959
601
656
698
54
476
791
549
188
763
654
662
264
265
501
141
552
180
1134
1034
945
830
201
255
527
636
1279
110
857
274
851
575
1100
220
281
944
877
91
234
911
195
681
52
406
1239
222
181
1135
1314
303
954
11
322
714
562
15...

output:

? 1128 593
? 697 1248
? 484 359
? 1467 217
? 249 183
? 1126 1487
? 1416 1285
? 244 1302
? 972 1369
? 1002 376
? 434 1500
? 32 1109
? 18 133
? 289 352
? 486 1268
? 767 751
? 821 1081
? 160 1433
? 959 1334
? 601 1384
? 656 950
? 1347 698
? 54 618
? 476 771
? 1380 791
? 549 964
? 188 883
? 1424 763
? 6...

result:

points 0.48132267450 points  0.48132267450 n = 1500, you used 2266 queries

Test #113:

score: 35.9225
Acceptable Answer
time: 18ms
memory: 12616kb

input:

1500
1150
41
1136
484
364
28
397
134
1121
11
698
571
25
107
244
1147
32
737
518
959
322
471
175
6
900
706
703
53
337
452
313
57
946
507
264
245
632
334
960
845
728
208
811
273
70
1159
837
386
872
148
995
349
588
1231
353
1219
620
58
19
1037
249
863
61
1416
135
1218
131
161
568
593
329
724
425
43
188...

output:

? 1328 1150
? 1349 41
? 1464 1136
? 484 1457
? 364 1099
? 28 405
? 397 1450
? 931 134
? 1121 1181
? 1356 11
? 1472 698
? 1015 571
? 25 581
? 685 107
? 244 555
? 1147 1429
? 813 32
? 1014 737
? 518 1152
? 959 1498
? 322 761
? 471 1204
? 1074 175
? 6 1449
? 900 1153
? 1417 706
? 703 1122
? 53 1053
? 3...

result:

points 0.44903070230 points  0.44903070230 n = 1500, you used 2450 queries

Test #114:

score: 35.4397
Acceptable Answer
time: 10ms
memory: 12656kb

input:

1500
398
461
226
182
24
892
636
208
290
159
657
672
296
20
384
1128
690
129
712
920
474
167
123
190
559
898
488
177
135
234
371
114
490
39
1066
386
758
780
1129
730
295
930
955
521
411
438
710
580
873
813
1019
239
113
346
1057
44
117
716
132
1278
359
261
1241
279
422
420
258
277
385
596
1136
877
727...

output:

? 1455 977
? 1404 606
? 912 1289
? 1492 1344
? 41 302
? 1249 1149
? 1488 1276
? 1385 318
? 128 268
? 1057 1420
? 866 987
? 283 568
? 833 401
? 850 1062
? 908 594
? 758 1222
? 349 1341
? 984 649
? 139 1275
? 190 868
? 341 719
? 1018 891
? 1305 204
? 1437 779
? 1022 743
? 959 457
? 1077 133
? 1403 917...

result:

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

Test #115:

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

input:

1500
248
370
96
557
220
1297
46
232
420
723
73
78
203
413
341
573
59
686
144
94
1107
250
1126
206
609
27
308
703
1208
365
147
217
155
337
673
207
657
1018
312
68
36
457
421
905
105
108
405
63
7
512
397
730
211
637
799
429
26
721
621
534
511
650
62
987
356
491
577
633
726
771
84
648
433
230
347
554
9...

output:

? 248 1362
? 370 1165
? 940 96
? 557 1154
? 220 843
? 1297 1493
? 46 1024
? 232 402
? 420 814
? 957 723
? 73 1384
? 78 610
? 203 1441
? 413 593
? 341 1127
? 573 850
? 787 59
? 686 834
? 1057 144
? 94 436
? 1107 1354
? 250 900
? 1126 1267
? 1079 206
? 609 707
? 27 1326
? 308 719
? 703 953
? 1208 1420...

result:

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

Test #116:

score: 33.5362
Acceptable Answer
time: 15ms
memory: 12648kb

input:

1500
848
166
804
121
318
980
574
845
379
301
79
743
1373
173
5
340
634
994
463
84
210
809
803
249
541
1146
358
51
201
217
669
1055
881
255
226
442
806
110
1118
1194
753
406
73
377
213
241
194
61
351
605
1021
231
657
486
362
37
639
626
177
808
149
733
108
357
763
961
252
642
542
8
492
1409
43
554
6
3...

output:

? 848 960
? 1309 166
? 804 1218
? 1171 121
? 825 318
? 1084 980
? 1457 574
? 845 1022
? 536 379
? 301 1493
? 79 100
? 743 1393
? 1373 1471
? 829 173
? 1177 5
? 456 340
? 634 1451
? 1247 994
? 839 463
? 84 1389
? 210 347
? 1380 809
? 803 1152
? 249 1481
? 541 697
? 1146 1227
? 358 466
? 1455 51
? 201...

result:

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

Test #117:

score: 33.4229
Acceptable Answer
time: 17ms
memory: 12744kb

input:

1500
989
174
49
100
269
555
895
1041
552
182
484
289
833
155
279
137
168
475
530
594
199
304
104
699
380
531
750
1095
546
175
1035
409
440
333
320
59
1071
202
1150
286
308
473
1
342
326
1374
523
108
422
433
128
452
581
93
275
373
27
259
189
744
376
86
504
540
1066
69
652
557
6
229
532
220
190
1023
5...

output:

? 1018 989
? 1083 174
? 49 1486
? 100 1310
? 269 717
? 555 768
? 1010 895
? 1399 1041
? 552 1425
? 1100 182
? 484 1005
? 289 1467
? 1024 833
? 155 1022
? 807 279
? 137 614
? 305 168
? 475 1155
? 1366 530
? 594 612
? 401 199
? 587 304
? 1202 104
? 1182 699
? 1240 380
? 861 531
? 1160 750
? 1095 1322
...

result:

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