QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#765484#8267. Staring Contest_8_8_#50.465379 20ms12968kbC++204.1kb2024-11-20 14:25:252024-11-20 14:25:25

Judging History

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

  • [2024-11-20 14:25:25]
  • 评测
  • 测评结果:50.465379
  • 用时:20ms
  • 内存:12968kb
  • [2024-11-20 14:25:25]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;

const int N = (int)1500  + 12;

const ll inf = (ll)1e18;

int c = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(123121);
int n, p, res[N], a[N];
bool loc = 0;
int mem[N][N];
int get(int i, int j) {
    if(mem[i][j] != -1) return mem[i][j];   
    c++;
    if(loc) return min(a[i], a[j]);
    cout << "? " << i << ' ' << j << endl;
    int x;
    cin >> x;
    return mem[i][j] = mem[j][i] = x;
}
void solve(vector<int> x) {

    if((int)x.size() <= 1) return;
    if((int)x.size() == 2) {
        int val = get(x[0], x[1]);
        res[x[0]] = res[x[1]] = val;
        return;
    }
    if((int)x.size() == 3) {
        int val = get(x[0], x[1]);
        int val1 = get(x[1], x[2]);
        if(val == val1) {
            res[x[1]] = val;
            solve({x[0], x[2]});
            return;
        } else {
            res[x[0]] = val;
            res[x[1]] = max(val, val1);
            res[x[2]] = val1;
        }
        return;
    }
    vector<array<int, 3>> f;
    vector<int> y;
    vector<int> vis(n + 1, 0);
    while(!x.empty()) {
        int j = x.back();
        x.pop_back();
        if(vis[j]) continue;
        bool ok = 0;
        for(int r = 0; r < (int)x.size() - 1; r++) {
            if(mem[x[r]][j] != -1) {
                f.push_back({get(x[r], j), x[r], j});
                vis[x[r]] = 1;
                ok = 1;
                break;
            }
        }
        if(!ok) {
            y.push_back(j);
        }
    }
    x = y;
    int m = (int)x.size();
    vector<int> nx;
    if(m & 1) {
        x.pop_back();
    }
    m--;
    for(int i = 0; i < m; i += 2) {
        f.push_back({get(x[i], x[i + 1]), x[i], x[i + 1]});
    }
    array<int, 3> bf = f.back();
    f.pop_back();
    while(!f.empty()) {
        array<int, 3> nv = f.back();
        f.pop_back();
        int val = get(nv[1], bf[1]);
        if(val == nv[0]) {
            res[nv[1]] = val;
        } else if(val == bf[0]) {
            res[bf[1]] = val;
            bf = nv;
        } else {
            if(nv[0] < bf[0]) res[nv[2]] = nv[0];
            else{
                res[bf[2]] = bf[0];
                bf = nv;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!res[i]) {
            nx.push_back(i);
        }
    }
    // assert((int)nx.size() <= (int)x.size() / 2 + 2);
    solve(nx);
}
bool check() {
    int c = 0;
    for(int i = 1; i <= n; i++) {
        if(res[i] > a[i]) return false;
        if(res[i] < a[i]) c++;
    }
    return (c <= 1);
}
bool str = 0;
void test() {
    memset(mem, -1, sizeof(mem));
    for(int i = 1; i <= n; i++) {
        res[i] = 0;
    }
    if(!str) {
        cin >> n;
        if(loc) {
            for(int i = 1; i <= n; i++) {
                cin >> a[i];
            }
        }
    }
    vector<int> f(n);
    iota(f.begin(), f.end(), 1);
    // shuffle(f.begin(), f.end(), rng);
    solve(f);
    int mx = 0;
    for(int i = 1; i <= n; i++) {
        mx = max(mx ,res[i]);
    }
    for(int i =1; i <= n; i++) {
        if(!res[i]) res[i] = mx;
    }
    if(!str) {
        cout << "! ";
        for(int i = 1; i <= n; i++) {
            cout << res[i] << ' ';
        }
    }
}

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

    while(t--) 
        test();

    return 0;
}

詳細信息

Subtask #1:

score: 9
Accepted

Test #1:

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

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #2:

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

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

input:

2
1

output:

? 1 2
! 1 1 

result:

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

Test #4:

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

input:

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

output:

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

result:

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

Test #5:

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

input:

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

output:

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

result:

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

Test #6:

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

input:

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

output:

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

result:

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

Test #7:

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

input:

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

output:

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

result:

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

Test #8:

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

input:

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

output:

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

result:

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

Test #9:

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

input:

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

output:

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

result:

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

Test #10:

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

input:

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

output:

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

result:

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

Test #11:

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

input:

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

output:

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

result:

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

Test #12:

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

input:

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

output:

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

result:

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

Test #13:

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

input:

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

output:

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

result:

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

Test #14:

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

input:

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

output:

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

result:

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

Test #15:

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

input:

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

output:

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

result:

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

Test #16:

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

input:

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

output:

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

result:

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

Test #17:

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

input:

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

output:

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

result:

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

Test #18:

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

input:

50
86399
86397
86395
86393
86391
86389
86386
86384
86382
86380
86378
86376
86374
86372
86370
86368
86366
86364
86362
86360
86358
86356
86354
86352
86350
86351
86353
86355
86357
86359
86361
86363
86365
86367
86369
86371
86373
86375
86377
86379
86381
86383
86385
86388
86390
86392
86394
86396
86398
863...

output:

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

result:

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

Test #19:

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

input:

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

output:

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

result:

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

Test #20:

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

input:

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

output:

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

result:

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

Test #21:

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

input:

50
84766
84349
82221
80336
78428
76687
75306
74688
73709
70891
69824
68114
67305
66780
65062
61154
59551
58019
57154
56501
54962
53250
52428
51290
50293
50918
52391
52604
54556
56134
56991
57364
58109
60767
62431
66090
67289
67638
68459
70252
72805
73877
75191
75331
77305
78936
80975
82385
84732
823...

output:

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

result:

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

Test #22:

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

input:

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

output:

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

result:

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

Test #23:

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

input:

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

output:

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

result:

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

Test #24:

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

input:

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

output:

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

result:

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

Test #25:

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

input:

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

output:

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

result:

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

Test #26:

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

input:

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

output:

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

result:

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

Test #27:

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

input:

50
57318
58717
53213
72585
61968
74083
54250
51658
55504
82479
66448
68422
65477
62248
67146
58746
75075
72620
58357
62990
79358
61401
53454
53987
73081
53987
53454
61401
73081
62990
67069
72620
75075
81710
72987
70576
65477
80461
66448
81710
55504
51658
70928
76671
82913
72585
53213
58717
82913
712...

output:

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

result:

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

Test #28:

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

input:

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

output:

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

result:

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

Test #29:

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

input:

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

output:

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

result:

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

Test #30:

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

input:

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

output:

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

result:

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

Test #31:

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

input:

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

output:

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

result:

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

Test #32:

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

input:

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

output:

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

result:

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

Test #33:

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

input:

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

output:

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

result:

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

Test #34:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #35:

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

input:

4
5
2
3
3

output:

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

result:

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

Test #36:

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

input:

4
3
2
5
3

output:

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

input:

4
3
2
3
5

output:

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

input:

4
3
2
5
3

output:

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

result:

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

Test #39:

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

input:

4
3
2
3
5

output:

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

result:

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

Test #40:

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

input:

4
5
2
2
3

output:

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

result:

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

Test #41:

score: 9
Accepted
time: 5ms
memory: 12504kb

input:

4
5
2
2
3

output:

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

input:

4
2
3
5

output:

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

result:

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

Test #43:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #44:

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

input:

4
2
3
5

output:

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

result:

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

Test #45:

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

input:

4
2
3
2
5

output:

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

result:

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

Test #46:

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

input:

4
3
2
2
3
5

output:

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

input:

4
3
2
2
5

output:

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

input:

4
2
3
3
2
5

output:

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

result:

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

Test #49:

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

input:

4
2
3
2
3
5

output:

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

result:

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

Test #50:

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

input:

4
2
5
3

output:

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

result:

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

Test #51:

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

input:

4
2
5
2
3

output:

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

result:

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

Test #52:

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

input:

4
3
2
2
3
5

output:

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

result:

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

Test #53:

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

input:

4
3
2
2
5

output:

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

result:

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

Test #54:

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

input:

4
2
3
3
2
5

output:

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

result:

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

Test #55:

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

input:

4
2
3
2
3
5

output:

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

result:

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

Test #56:

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

input:

4
2
5
3

output:

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

result:

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

Test #57:

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

input:

4
2
5
2
3

output:

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

input:

1000
999
997
995
993
991
989
987
985
983
981
979
977
975
973
971
969
967
965
963
961
959
957
955
953
951
949
947
945
943
941
939
937
935
933
931
929
927
925
923
921
919
917
915
913
911
909
907
905
903
901
899
897
895
893
891
889
887
885
883
881
879
877
875
873
871
869
867
865
863
861
859
857
855
853...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #59:

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

input:

1000
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
125
127
129
131
133
135
137
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
17...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #60:

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

input:

1000
2
6
10
14
18
22
26
30
34
38
42
46
50
54
58
62
66
70
74
78
82
86
90
94
98
102
106
110
114
118
122
126
130
134
138
142
146
150
154
158
162
166
170
174
178
182
186
190
194
198
202
206
210
214
218
222
226
230
234
238
242
246
250
254
258
262
266
270
274
278
282
286
290
294
298
302
306
310
314
318
32...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #61:

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

input:

1000
1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145
149
153
157
161
165
169
173
177
181
185
189
193
197
201
205
209
213
217
221
225
229
233
237
241
245
249
253
257
261
265
269
273
277
281
285
289
293
297
301
305
309
313
317
321...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #62:

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

input:

1000
997
993
989
985
981
977
973
969
965
961
957
953
949
945
941
937
933
929
925
921
917
913
909
905
901
897
893
889
885
881
877
873
869
865
861
857
853
849
845
841
837
833
829
825
821
817
813
809
805
801
797
793
789
785
781
777
773
769
765
761
757
753
749
745
741
737
733
729
725
721
717
713
709
705...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #63:

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

input:

1000
998
994
990
986
982
978
974
970
966
962
958
954
950
946
942
938
934
930
926
922
918
914
910
906
902
898
894
890
886
882
878
874
870
866
862
858
854
850
846
842
838
834
830
826
822
818
814
810
806
802
798
794
790
786
782
778
774
770
766
762
758
754
750
746
742
738
734
730
726
722
718
714
710
706...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #64:

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

input:

1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #65:

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

input:

1000
500
499
498
497
496
495
494
493
492
491
490
489
488
487
486
485
484
483
482
481
480
479
478
477
476
475
474
473
472
471
470
469
468
467
466
465
464
463
462
461
460
459
458
457
456
455
454
453
452
451
450
449
448
447
446
445
444
443
442
441
440
439
438
437
436
435
434
433
432
431
430
429
428
427...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #66:

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

input:

1000
998
996
994
992
990
988
986
984
982
980
978
976
974
972
970
968
966
964
962
960
958
956
954
952
950
948
946
944
942
940
938
936
934
932
930
928
926
924
922
920
918
916
914
912
910
908
906
904
902
900
898
896
894
892
890
888
886
884
882
880
878
876
874
872
870
868
866
864
862
860
858
856
854
852...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #67:

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

input:

1000
1
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50
52
54
56
58
60
62
64
66
68
70
72
74
76
78
80
82
84
86
88
90
92
94
96
98
100
102
104
106
108
110
112
114
116
118
120
122
124
126
128
130
132
134
136
138
140
142
144
146
148
150
152
154
156
158
160
162
164
166
168
170
172
17...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #68:

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

input:

300
299
297
295
293
291
289
287
285
283
281
279
277
275
273
271
269
267
265
263
261
259
257
255
253
251
249
247
245
243
241
239
237
235
233
231
229
227
225
223
221
219
217
215
213
211
209
207
205
203
201
199
197
195
193
191
189
187
185
183
181
179
177
175
173
171
169
167
165
163
161
159
157
155
153
...

output:

? 300 299
? 298 297
? 296 295
? 294 293
? 292 291
? 290 289
? 288 287
? 286 285
? 284 283
? 282 281
? 280 279
? 278 277
? 276 275
? 274 273
? 272 271
? 270 269
? 268 267
? 266 265
? 264 263
? 262 261
? 260 259
? 258 257
? 256 255
? 254 253
? 252 251
? 250 249
? 248 247
? 246 245
? 244 243
? 242 241
...

result:

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

Test #69:

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

input:

300
79
10
86
196
258
17
110
69
143
71
40
77
188
142
139
192
158
276
160
186
168
60
31
133
44
3
163
15
106
34
178
29
108
20
81
165
1
116
201
5
76
239
157
207
107
228
42
64
111
136
126
120
18
92
53
150
124
180
85
202
147
144
24
134
155
56
217
21
25
162
47
183
175
26
127
91
19
45
96
38
12
149
66
36
59
...

output:

? 300 299
? 298 297
? 296 295
? 294 293
? 292 291
? 290 289
? 288 287
? 286 285
? 284 283
? 282 281
? 280 279
? 278 277
? 276 275
? 274 273
? 272 271
? 270 269
? 268 267
? 266 265
? 264 263
? 262 261
? 260 259
? 258 257
? 256 255
? 254 253
? 252 251
? 250 249
? 248 247
? 246 245
? 244 243
? 242 241
...

result:

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

Test #70:

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

input:

1000
211
506
107
544
305
346
612
40
563
331
289
41
510
260
170
237
833
148
193
835
222
536
789
294
18
110
417
152
280
891
163
719
197
106
486
541
752
45
104
494
192
55
394
142
360
501
173
34
79
483
460
277
32
26
557
246
265
198
74
266
320
586
115
433
532
862
67
247
539
593
114
342
233
577
609
396
82...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #71:

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

input:

1000
1998
1996
1994
1990
1983
1977
1974
1970
1966
1964
1960
1956
1948
1946
1942
1940
1936
1933
1931
1929
1927
1924
1921
1916
1910
1907
1902
1900
1895
1891
1885
1879
1877
1874
1870
1866
1859
1855
1851
1846
1843
1838
1834
1831
1828
1826
1823
1821
1818
1816
1813
1811
1806
1803
1801
1798
1791
1788
1780
...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #72:

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

input:

1000
86399
86397
86395
86393
86391
86389
86387
86385
86383
86381
86379
86377
86375
86373
86371
86369
86367
86365
86363
86361
86359
86357
86355
86353
86351
86349
86347
86345
86343
86341
86339
86337
86335
86333
86331
86329
86327
86325
86323
86321
86319
86317
86315
86313
86311
86309
86307
86305
86303
8...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #73:

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

input:

1000
9977
9960
9953
9939
9932
9929
9903
9899
9897
9881
9859
9843
9832
9828
9821
9818
9810
9799
9788
9769
9762
9746
9737
9735
9721
9711
9688
9686
9676
9673
9663
9652
9645
9636
9630
9627
9622
9608
9591
9583
9580
9571
9566
9553
9536
9528
9516
9509
9498
9488
9481
9473
9454
9451
9446
9434
9430
9420
9415
...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #74:

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

input:

1000
5998
5995
5992
5989
5987
5984
5982
5973
5969
5967
5963
5960
5957
5952
5949
5939
5937
5933
5927
5925
5921
5911
5909
5907
5905
5900
5898
5895
5891
5888
5885
5881
5877
5872
5863
5859
5857
5852
5849
5846
5842
5839
5836
5834
5829
5826
5820
5817
5815
5807
5805
5798
5796
5794
5789
5783
5777
5774
5765
...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #75:

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

input:

1000
86344
86263
86149
85960
85754
85695
85687
85532
85457
85365
85298
85220
85144
85039
84933
84904
84868
84813
84737
84726
84677
84630
84558
84406
84381
84341
84251
84125
84095
84028
83903
83797
83708
83681
83671
83520
83447
83379
83326
83193
83128
82937
82900
82857
82790
82582
82483
82472
82394
8...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #76:

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

input:

1000
492
314
278
20
253
411
465
293
246
851
81
869
49
388
755
2
521
426
194
180
221
150
331
599
143
368
460
537
199
27
683
344
778
469
227
378
360
666
53
610
929
130
587
114
179
256
351
176
647
212
139
863
48
602
57
349
87
434
171
75
347
563
209
429
70
25
317
573
148
329
16
335
440
218
328
591
495
2...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #77:

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

input:

1000
982
706
717
743
444
1033
880
33
112
1196
740
150
296
1085
979
148
1555
311
572
1019
161
970
822
272
558
1235
792
1727
684
962
677
213
650
1581
370
947
1415
37
672
539
164
317
854
10
600
23
222
745
1567
1335
877
107
1710
871
1115
1228
1099
1663
246
496
44
1330
271
1204
66
1061
50
249
1216
342
23...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #78:

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

input:

1000
85574
85759
85472
85686
85521
85858
86028
85901
85573
85552
85518
85722
85953
85457
85514
85938
85409
85890
85870
85993
85717
85916
85515
85511
85435
85749
86045
86231
85466
86351
85488
85860
85434
85634
85745
85968
86151
85653
85925
85507
85484
85622
85828
85447
86107
85445
85898
85411
85687
8...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #79:

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

input:

1000
7684
8301
6002
6166
7076
7575
6613
5577
5447
8502
6744
5682
6337
7687
7670
7268
5530
8262
5213
8537
9775
6622
5300
5135
7036
6545
6733
8901
6390
5714
7070
5047
5771
5419
6155
5579
7020
6402
7970
7107
9345
6775
5159
6585
8102
7114
5426
9795
6039
5511
6331
6911
7895
5430
8892
8524
5158
5592
9434
...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #80:

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

input:

1000
4850
5437
4680
4279
4567
4312
4570
4146
4399
4088
5349
4718
4339
4104
4313
4035
5830
4140
4576
5035
4323
4510
4420
5694
4896
5205
4599
5373
5570
5243
5194
4780
4505
4447
5076
5344
4495
5293
4522
4165
4294
4614
4565
5119
4971
4335
4290
4917
4289
4069
4478
5328
4082
4967
4394
4125
4649
4907
4598
...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #81:

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

input:

1000
65015
54752
76510
59338
63140
74731
68129
51236
63444
81246
63379
53060
65732
62672
64988
65557
54208
59527
58512
63170
57423
69137
57581
51978
52411
83574
55213
61439
50628
70859
55218
52281
60073
50304
62203
67091
58631
77158
50521
80491
57496
65810
53573
57068
61058
67124
78270
63472
50216
5...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #82:

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

input:

1000
1
997
995
993
991
989
987
985
983
981
979
977
975
973
971
969
967
965
963
961
959
957
955
953
951
949
947
945
943
941
939
937
935
933
931
929
927
925
923
921
919
917
915
913
911
909
907
905
903
901
899
897
895
893
891
889
887
885
883
881
879
877
875
873
871
869
867
865
863
861
859
857
855
853
8...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #83:

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

input:

1000
1
997
995
993
991
989
987
985
983
981
979
977
975
973
971
969
967
965
963
961
959
957
955
953
951
949
947
945
943
941
939
937
935
933
931
929
927
925
923
921
919
917
915
913
911
909
907
905
903
901
899
897
895
893
891
889
887
885
883
881
879
877
875
873
871
869
867
865
863
861
859
857
855
853
8...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #84:

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

input:

1000
999
26
6
381
680
509
879
217
230
344
219
204
148
11
507
182
640
263
305
798
492
212
323
23
326
500
92
106
380
604
289
646
291
884
85
267
71
231
15
271
338
58
372
253
120
598
816
538
808
89
508
748
343
205
282
395
431
430
489
272
417
177
894
150
612
854
107
112
452
22
561
7
104
189
455
28
170
59...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #85:

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

input:

1000
999
997
995
993
991
989
987
985
983
981
979
977
975
973
971
969
967
965
963
961
959
957
955
953
951
949
947
945
943
941
939
937
935
933
931
929
927
925
923
921
919
917
915
913
911
909
907
905
903
901
899
897
895
893
891
889
887
885
883
881
879
877
875
873
871
869
867
865
863
861
859
857
855
853...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #86:

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

input:

1000
1
997
995
993
991
989
987
985
983
981
979
977
975
973
971
969
967
965
963
961
959
957
955
953
951
949
947
945
943
941
939
937
935
933
931
929
927
925
923
921
919
917
915
913
911
909
907
905
903
901
899
897
895
893
891
889
887
885
883
881
879
877
875
873
871
869
867
865
863
861
859
857
855
853
8...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Test #87:

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

input:

1000
1
997
995
993
991
989
987
985
983
981
979
977
975
973
971
969
967
965
963
961
959
957
955
953
951
949
947
945
943
941
939
937
935
933
931
929
927
925
923
921
919
917
915
913
911
909
907
905
903
901
899
897
895
893
891
889
887
885
883
881
879
877
875
873
871
869
867
865
863
861
859
857
855
853
8...

output:

? 1000 999
? 998 997
? 996 995
? 994 993
? 992 991
? 990 989
? 988 987
? 986 985
? 984 983
? 982 981
? 980 979
? 978 977
? 976 975
? 974 973
? 972 971
? 970 969
? 968 967
? 966 965
? 964 963
? 962 961
? 960 959
? 958 957
? 956 955
? 954 953
? 952 951
? 950 949
? 948 947
? 946 945
? 944 943
? 942 941...

result:

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

Subtask #3:

score: 30.4654
Acceptable Answer

Test #88:

score: 38.7591
Acceptable Answer
time: 13ms
memory: 12764kb

input:

1500
1499
1497
1495
1493
1491
1489
1487
1485
1483
1481
1479
1477
1475
1473
1471
1469
1467
1465
1463
1461
1459
1457
1455
1453
1451
1449
1447
1445
1443
1441
1439
1437
1435
1433
1431
1429
1427
1425
1423
1421
1419
1417
1415
1413
1411
1409
1407
1405
1403
1401
1399
1397
1395
1393
1391
1389
1387
1385
1383
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #89:

score: 30.4734
Acceptable Answer
time: 4ms
memory: 12936kb

input:

1500
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
125
127
129
131
133
135
137
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
17...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.38091747620 points  0.38091747620 n = 1500, you used 2996 queries

Test #90:

score: 33.8616
Acceptable Answer
time: 18ms
memory: 12760kb

input:

1500
2
6
10
14
18
22
26
30
34
38
42
46
50
54
58
62
66
70
74
78
82
86
90
94
98
102
106
110
114
118
122
126
130
134
138
142
146
150
154
158
162
166
170
174
178
182
186
190
194
198
202
206
210
214
218
222
226
230
234
238
242
246
250
254
258
262
266
270
274
278
282
286
290
294
298
302
306
310
314
318
32...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.42326978520 points  0.42326978520 n = 1500, you used 2628 queries

Test #91:

score: 33.8616
Acceptable Answer
time: 0ms
memory: 12932kb

input:

1500
1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125
129
133
137
141
145
149
153
157
161
165
169
173
177
181
185
189
193
197
201
205
209
213
217
221
225
229
233
237
241
245
249
253
257
261
265
269
273
277
281
285
289
293
297
301
305
309
313
317
321...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.42326978520 points  0.42326978520 n = 1500, you used 2628 queries

Test #92:

score: 30.4975
Acceptable Answer
time: 19ms
memory: 12696kb

input:

1500
1497
1493
1489
1485
1481
1477
1473
1469
1465
1461
1457
1453
1449
1445
1441
1437
1433
1429
1425
1421
1417
1413
1409
1405
1401
1397
1393
1389
1385
1381
1377
1373
1369
1365
1361
1357
1353
1349
1345
1341
1337
1333
1329
1325
1321
1317
1313
1309
1305
1301
1297
1293
1289
1285
1281
1277
1273
1269
1265
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.38121858040 points  0.38121858040 n = 1500, you used 2993 queries

Test #93:

score: 30.4975
Acceptable Answer
time: 5ms
memory: 12700kb

input:

1500
1498
1494
1490
1486
1482
1478
1474
1470
1466
1462
1458
1454
1450
1446
1442
1438
1434
1430
1426
1422
1418
1414
1410
1406
1402
1398
1394
1390
1386
1382
1378
1374
1370
1366
1362
1358
1354
1350
1346
1342
1338
1334
1330
1326
1322
1318
1314
1310
1306
1302
1298
1294
1290
1286
1282
1278
1274
1270
1266
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.38121858040 points  0.38121858040 n = 1500, you used 2993 queries

Test #94:

score: 33.8935
Acceptable Answer
time: 9ms
memory: 12968kb

input:

1500
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

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

Test #95:

score: 30.4734
Acceptable Answer
time: 7ms
memory: 12648kb

input:

1500
750
749
748
747
746
745
744
743
742
741
740
739
738
737
736
735
734
733
732
731
730
729
728
727
726
725
724
723
722
721
720
719
718
717
716
715
714
713
712
711
710
709
708
707
706
705
704
703
702
701
700
699
698
697
696
695
694
693
692
691
690
689
688
687
686
685
684
683
682
681
680
679
678
677...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.38091747620 points  0.38091747620 n = 1500, you used 2996 queries

Test #96:

score: 38.8233
Acceptable Answer
time: 16ms
memory: 12940kb

input:

1500
1498
1496
1494
1492
1490
1488
1486
1484
1482
1480
1478
1476
1474
1472
1470
1468
1466
1464
1462
1460
1458
1456
1454
1452
1450
1448
1446
1444
1442
1440
1438
1436
1434
1432
1430
1428
1426
1424
1422
1420
1418
1416
1414
1412
1410
1408
1406
1404
1402
1400
1398
1396
1394
1392
1390
1388
1386
1384
1382
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.485291160 points  0.485291160 n = 1500, you used 2246 queries

Test #97:

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

input:

1500
1
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50
52
54
56
58
60
62
64
66
68
70
72
74
76
78
80
82
84
86
88
90
92
94
96
98
100
102
104
106
108
110
112
114
116
118
120
122
124
126
128
130
132
134
136
138
140
142
144
146
148
150
152
154
156
158
160
162
164
166
168
170
172
17...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.38081724230 points  0.38081724230 n = 1500, you used 2997 queries

Test #98:

score: 40.0948
Acceptable Answer
time: 11ms
memory: 12588kb

input:

1500
1159
194
696
507
299
665
170
102
582
428
419
365
1333
370
624
8
167
312
336
44
497
718
327
30
168
325
1122
85
872
538
404
1291
1420
118
619
627
1047
790
6
394
551
269
746
198
772
134
40
852
362
11
640
237
157
520
1015
407
1087
131
480
173
39
490
225
366
670
268
272
791
302
1157
32
764
375
43
93...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.50118462950 points  0.50118462950 n = 1500, you used 2171 queries

Test #99:

score: 40.2931
Acceptable Answer
time: 11ms
memory: 12692kb

input:

1500
469
359
609
193
297
1039
1242
392
233
126
978
658
774
557
64
218
146
56
625
408
125
422
685
517
647
136
67
740
112
285
323
55
929
215
1311
1120
540
641
1129
118
833
339
440
565
603
187
201
902
1030
449
61
398
40
183
347
907
613
334
484
207
982
311
572
598
424
113
280
72
970
467
849
322
1197
299...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.50366402470 points  0.50366402470 n = 1500, you used 2160 queries

Test #100:

score: 39.5187
Acceptable Answer
time: 11ms
memory: 12912kb

input:

1500
464
428
810
529
533
381
473
472
625
1361
32
193
679
215
393
696
1054
204
251
79
357
94
120
841
629
448
241
787
1254
105
255
400
93
526
155
963
110
415
912
468
367
54
842
1005
269
307
228
516
697
46
12
621
535
409
71
511
180
1039
72
266
140
82
136
773
938
264
976
465
360
939
1099
234
1194
403
60...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.49398324660 points  0.49398324660 n = 1500, you used 2204 queries

Test #101:

score: 38.7591
Acceptable Answer
time: 8ms
memory: 12700kb

input:

1500
2995
2992
2989
2983
2980
2975
2963
2961
2957
2952
2948
2943
2938
2933
2929
2925
2921
2919
2915
2912
2910
2907
2905
2902
2896
2893
2891
2887
2885
2878
2874
2869
2867
2862
2854
2850
2839
2833
2828
2819
2817
2812
2808
2805
2803
2799
2796
2791
2785
2783
2780
2776
2772
2769
2767
2765
2761
2758
2754
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #102:

score: 38.7591
Acceptable Answer
time: 7ms
memory: 12936kb

input:

1500
86399
86397
86395
86393
86391
86389
86387
86385
86383
86381
86379
86377
86375
86373
86371
86369
86367
86365
86363
86361
86359
86357
86355
86353
86351
86349
86347
86345
86343
86341
86339
86337
86335
86333
86331
86329
86327
86325
86323
86321
86319
86317
86315
86313
86311
86309
86307
86305
86303
8...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #103:

score: 38.7591
Acceptable Answer
time: 4ms
memory: 12640kb

input:

1500
9997
9993
9989
9981
9977
9971
9968
9964
9960
9953
9946
9941
9939
9936
9933
9924
9922
9919
9916
9909
9902
9898
9894
9888
9875
9873
9871
9866
9854
9851
9845
9841
9838
9827
9815
9808
9805
9801
9796
9782
9772
9764
9737
9717
9714
9704
9700
9698
9664
9658
9648
9641
9637
9634
9629
9619
9607
9605
9600
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #104:

score: 38.7591
Acceptable Answer
time: 5ms
memory: 12936kb

input:

1500
5999
5997
5993
5991
5989
5987
5985
5983
5981
5978
5976
5974
5972
5969
5967
5965
5963
5961
5958
5955
5951
5949
5947
5945
5943
5941
5939
5937
5933
5931
5927
5925
5922
5918
5915
5912
5910
5908
5906
5902
5900
5898
5896
5894
5891
5889
5887
5884
5882
5880
5877
5875
5872
5870
5868
5865
5863
5860
5858
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #105:

score: 38.7591
Acceptable Answer
time: 20ms
memory: 12864kb

input:

1500
86371
86338
86291
86242
86209
86146
86072
86047
86030
85974
85850
85804
85795
85751
85667
85572
85521
85377
85371
85353
85331
85298
85272
85266
85254
85042
85001
84954
84937
84801
84735
84705
84610
84573
84558
84503
84455
84404
84283
84224
84179
84142
84087
84046
83924
83916
83894
83850
83836
8...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #106:

score: 40.6063
Acceptable Answer
time: 0ms
memory: 12720kb

input:

1500
138
30
944
626
92
188
732
86
421
524
76
80
829
139
980
1034
125
571
195
555
66
353
532
315
1191
719
866
1091
363
212
440
503
61
263
1107
270
523
1156
817
1338
581
475
51
656
32
455
1283
892
922
40
227
957
284
488
763
1087
854
529
267
1148
20
757
510
117
842
57
210
609
774
26
978
742
173
802
666...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.50757829140 points  0.50757829140 n = 1500, you used 2143 queries

Test #107:

score: 41.4769
Acceptable Answer
time: 8ms
memory: 12688kb

input:

1500
389
523
520
947
125
1071
356
1175
647
445
368
83
475
943
172
668
348
25
884
512
712
367
1616
106
1100
778
576
360
521
1179
1552
282
1134
303
1846
222
951
618
1010
818
1796
1523
738
1
993
572
280
86
869
595
1578
173
183
676
908
639
1065
380
897
8
744
635
330
2
1748
386
54
114
1557
193
1383
85
53...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.51846138690 points  0.51846138690 n = 1500, you used 2098 queries

Test #108:

score: 40.6811
Acceptable Answer
time: 0ms
memory: 12748kb

input:

1500
84910
85022
85827
84932
85054
84933
84936
86021
85101
85526
85750
85852
85595
85215
84984
85565
85219
85010
85021
85166
85156
85639
84944
85035
86123
85093
85108
85043
85991
85080
85313
85076
85415
86360
85589
85647
85929
85047
85508
85746
84950
85868
85407
85462
85019
85924
84975
85147
85185
8...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.50851433180 points  0.50851433180 n = 1500, you used 2139 queries

Test #109:

score: 40.0591
Acceptable Answer
time: 8ms
memory: 12748kb

input:

1500
6040
5355
5564
5650
5202
5643
7677
6236
7251
7476
7295
8615
8248
7112
5658
5158
6378
5502
6994
9587
6131
5072
5987
6019
7449
6854
5268
7595
5192
6299
5709
5929
7035
8711
7818
7872
6835
5040
5444
7426
5092
5860
5867
6396
6470
5799
5989
6146
6564
5911
6666
7160
5731
5304
5704
8083
7100
6735
5331
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.50073820060 points  0.50073820060 n = 1500, you used 2173 queries

Test #110:

score: 36.8819
Acceptable Answer
time: 5ms
memory: 12848kb

input:

1500
4422
5351
4133
4369
4312
4749
4123
5253
4444
4797
5223
4864
4846
4574
4811
4463
5368
4378
4164
5366
4694
4598
4255
4545
4695
4890
4781
4071
5593
4343
4431
4910
4064
4930
4803
4985
4568
5210
4009
4446
4922
4402
4667
4155
4361
4831
4832
4765
4257
5020
4793
4558
4609
4168
4026
4073
4476
5362
5700
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.46102395110 points  0.46102395110 n = 1500, you used 2377 queries

Test #111:

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

input:

1500
71398
54763
63993
51770
77251
78313
54730
64336
52072
65850
52640
56762
61708
68150
60969
66861
51477
52684
72788
51645
51988
64110
71151
74005
57342
54794
56561
72365
57629
56372
61981
67181
62286
57751
74700
51548
54535
57288
55451
61325
71047
67425
52094
64176
50622
57678
75688
57753
67168
5...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.52460559060 points  0.52460559060 n = 1500, you used 2074 queries

Test #112:

score: 80
Accepted
time: 8ms
memory: 12708kb

input:

1500
1
1497
1495
1493
1491
1489
1487
1485
1483
1481
1479
1477
1475
1473
1471
1469
1467
1465
1463
1461
1459
1457
1455
1453
1451
1449
1447
1445
1443
1441
1439
1437
1435
1433
1431
1429
1427
1425
1423
1421
1419
1417
1415
1413
1411
1409
1407
1405
1403
1401
1399
1397
1395
1393
1391
1389
1387
1385
1383
138...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

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

Test #113:

score: 80
Accepted
time: 6ms
memory: 12596kb

input:

1500
1
1497
1495
1493
1491
1489
1487
1485
1483
1481
1479
1477
1475
1473
1471
1469
1467
1465
1463
1461
1459
1457
1455
1453
1451
1449
1447
1445
1443
1441
1439
1437
1435
1433
1431
1429
1427
1425
1423
1421
1419
1417
1415
1413
1411
1409
1407
1405
1403
1401
1399
1397
1395
1393
1391
1389
1387
1385
1383
138...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

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

Test #114:

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

input:

1500
1499
95
111
327
554
80
636
181
229
191
91
291
285
621
736
236
802
63
102
901
484
574
319
209
300
1232
799
52
150
487
526
366
195
727
871
219
256
415
235
310
159
400
81
399
6
598
392
2
177
269
257
503
93
54
848
160
438
208
340
1090
676
313
197
64
267
121
742
424
230
819
375
147
984
75
1207
361
5...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.53046779310 points  0.53046779310 n = 1500, you used 2052 queries

Test #115:

score: 38.7591
Acceptable Answer
time: 16ms
memory: 12700kb

input:

1500
1499
1497
1495
1493
1491
1489
1487
1485
1483
1481
1479
1477
1475
1473
1471
1469
1467
1465
1463
1461
1459
1457
1455
1453
1451
1449
1447
1445
1443
1441
1439
1437
1435
1433
1431
1429
1427
1425
1423
1421
1419
1417
1415
1413
1411
1409
1407
1405
1403
1401
1399
1397
1395
1393
1391
1389
1387
1385
1383
...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.4844890190 points  0.4844890190 n = 1500, you used 2250 queries

Test #116:

score: 38.6953
Acceptable Answer
time: 6ms
memory: 12704kb

input:

1500
1
1497
1495
1493
1491
1489
1487
1485
1483
1481
1479
1477
1475
1473
1471
1469
1467
1465
1463
1461
1459
1457
1455
1453
1451
1449
1447
1445
1443
1441
1439
1437
1435
1433
1431
1429
1427
1425
1423
1421
1419
1417
1415
1413
1411
1409
1407
1405
1403
1401
1399
1397
1395
1393
1391
1389
1387
1385
1383
138...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.48369114480 points  0.48369114480 n = 1500, you used 2254 queries

Test #117:

score: 38.6953
Acceptable Answer
time: 8ms
memory: 12868kb

input:

1500
1
1497
1495
1493
1491
1489
1487
1485
1483
1481
1479
1477
1475
1473
1471
1469
1467
1465
1463
1461
1459
1457
1455
1453
1451
1449
1447
1445
1443
1441
1439
1437
1435
1433
1431
1429
1427
1425
1423
1421
1419
1417
1415
1413
1411
1409
1407
1405
1403
1401
1399
1397
1395
1393
1391
1389
1387
1385
1383
138...

output:

? 1500 1499
? 1498 1497
? 1496 1495
? 1494 1493
? 1492 1491
? 1490 1489
? 1488 1487
? 1486 1485
? 1484 1483
? 1482 1481
? 1480 1479
? 1478 1477
? 1476 1475
? 1474 1473
? 1472 1471
? 1470 1469
? 1468 1467
? 1466 1465
? 1464 1463
? 1462 1461
? 1460 1459
? 1458 1457
? 1456 1455
? 1454 1453
? 1452 1451
...

result:

points 0.48369114480 points  0.48369114480 n = 1500, you used 2254 queries