QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#539625#8939. Permutationucup-team052#AC ✓203ms15720kbC++231.9kb2024-08-31 15:16:352024-08-31 15:16:38

Judging History

This is the latest submission verdict.

  • [2024-08-31 15:16:38]
  • Judged
  • Verdict: AC
  • Time: 203ms
  • Memory: 15720kb
Show
  • [2024-08-31 15:16:35]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define D(...) fprintf(stderr,__VA_ARGS__)
#define pb push_back
#define eb emplace_back
using namespace std;
using LL=long long;
const int N=1000005;
int dp[N],pos[N];
int len[N];
int query(int l,int r){
	printf("? %d %d\n",l,r);
	fflush(stdout);
	int ret;
	scanf("%d",&ret);
	return ret;
}
int solve(int l,int r,int ret=-1){
	if(l==r){
		return l;
	}
	int x=r-l+1;
	if(ret==-1){
		ret=query(l,r);
	}
	if(r-l+1==2){
		return l+r-ret;
	}
	if(ret<=l+pos[x]-1){
		int A=query(l,l+pos[x]-1);
		if(A==ret){
			return solve(l,l+pos[x]-1,ret);
		}else{
			return solve(l+pos[x],r,-1);
		}
	}else{
		int A=query(r-pos[x]+1,r);
		if(A==ret){
			return solve(r-pos[x]+1,r,ret);
		}else{
			return solve(l,r-pos[x],-1);
		}
	}
}
int main(){
#ifdef xay5421
	// freopen("a.in","r",stdin);
#endif
	int n=1000000;
	dp[1]=0;
	dp[2]=0;
	rep(i,3,n){
		dp[i]=1e9;
		/*rep(j,1,i-1){
			if(max(dp[j]+1,dp[i-j]+2)<dp[i]){
				dp[i]=max(dp[j]+1,dp[i-j]+2);
				pos=j;
			}
		}*/
		int l=(i+1)/2,r=i-1;
		while(l<=r){
			int j=(l+r)>>1;
			if(max(dp[j]+1,dp[i-j]+2)<dp[i]){
				dp[i]=max(dp[j]+1,dp[i-j]+2);
				len[i]=max(len[j]+j,len[i-j]+i);
				pos[i]=j;
			}else if(max(dp[j]+1,dp[i-j]+2)==dp[i]&&max(len[j]+j,len[i-j]+i)<len[i]){
				dp[i]=max(dp[j]+1,dp[i-j]+2);
				len[i]=max(len[j]+j,len[i-j]+i);
				pos[i]=j;
			}
			if(dp[j]+1>dp[i-j]+2){
				r=j-1;
			}else{
				l=j+1;
			}
		}
		
		assert(dp[i]+1<=int(ceil(1.5*log2(i))));
		assert(len[i]+i<=i*3);
		//D("dp[%d]=%d %d pos=%d len=%d need<=%d j=%.20f\n",i,dp[i]+1,int(ceil(1.5*log2(i))),pos[i],len[i]+i,i*3,1.*(i-pos[i])/i);
	}
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		int ret=solve(1,n);
		printf("! %d\n",ret);
		fflush(stdout);
	}
	return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 70ms
memory: 15568kb

input:

3
5
3
2
5
6
6
3
1
4
3
3

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 153ms
memory: 15648kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 130ms
memory: 15708kb

input:

10000
3
1
2
11
5
5
5
5
2
2
19
3
3
4
11
11
11
7
5
7
1
2
3
3
3
19
6
6
6
6
5
4
2
2
15
11
11
11
11
12
10
14
1
1
1
3
5
16
4
4
4
1
5
3
3
2
19
13
17
5
5
5
4
2
2
4
1
2
3
7
2
2
2
3
2
2
17
1
1
1
2
6
14
9
9
9
7
11
20
9
9
9
6
11
10
6
4
2
5
18
7
7
7
7
6
9
8
8
8
6
5
8
6
6
6
5
16
10
10
10
10
10
6
1
1
2
3
10
3
3
4
...

output:

? 1 3
? 1 2
! 3
? 1 11
? 1 6
? 3 6
? 5 6
! 6
? 1 2
! 1
? 1 19
? 1 11
? 1 6
? 7 11
? 9 11
? 10 11
! 10
? 1 7
? 4 7
? 1 3
? 1 2
! 3
? 1 3
? 2 3
! 2
? 1 19
? 1 11
? 1 6
? 3 6
? 5 6
? 3 4
! 3
? 1 2
! 1
? 1 15
? 7 15
? 7 12
? 9 12
? 11 12
? 9 10
! 9
? 1 14
? 1 8
? 1 5
? 1 3
? 4 5
! 4
? 1 16
? 1 10
? 1 6
...

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 148ms
memory: 15564kb

input:

10000
47
23
23
24
11
9
2
1
5
14
8
2
9
9
9
25
6
6
4
13
12
15
7
4
2
6
6
9
2
2
2
2
27
27
27
27
27
24
23
21
7
7
7
7
6
5
43
41
21
7
7
8
4
3
1
22
6
12
14
17
20
21
34
29
29
25
17
17
17
16
42
20
20
20
20
20
20
19
17
47
21
21
21
21
21
19
17
41
25
11
30
33
36
36
36
19
17
17
16
9
9
10
21
14
14
14
14
14
13
27
2...

output:

? 1 47
? 1 29
? 12 29
? 1 11
? 6 11
? 1 5
? 1 3
? 4 5
! 4
? 1 14
? 1 8
? 9 14
? 9 12
? 9 10
! 10
? 1 25
? 1 15
? 1 9
? 10 15
? 10 13
? 14 15
! 14
? 1 7
? 1 4
? 5 7
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? 1 2
! 1
? 1 27
? 12 27
? 18 27
? 22 27
? 24 27
? 22 23
! 22
? 1 21
? 1 13
? 1 8
? 4 8
? 6 8
? 4 5
! 4
? 1 ...

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 197ms
memory: 15688kb

input:

10000
100
47
61
93
96
71
71
71
71
71
9
2
2
2
1
4
53
46
35
6
6
6
6
6
6
33
3
16
31
31
31
29
32
82
60
41
29
29
29
28
23
24
26
88
39
8
59
59
59
59
59
59
71
24
29
59
49
65
65
64
61
92
52
45
88
88
88
88
85
91
91
24
11
11
9
5
5
6
3
66
51
51
45
29
28
39
40
42
92
43
43
50
20
20
20
20
20
19
48
1
1
1
1
5
9
9
9...

output:

? 1 100
? 1 61
? 62 100
? 77 100
? 62 76
? 68 76
? 68 73
? 68 71
? 70 71
! 70
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 3
? 1 53
? 22 53
? 1 21
? 1 13
? 1 8
? 4 8
? 4 6
? 5 6
! 5
? 1 33
? 1 20
? 21 33
? 26 33
? 29 33
? 29 31
? 32 33
! 33
? 1 82
? 33 82
? 1 32
? 14 32
? 22 32
? 27 32
? 22 26
? 22 24
? 25 26
! ...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 170ms
memory: 15720kb

input:

10000
50
10
10
10
10
6
2
3
5
50
11
11
9
23
23
23
22
25
50
44
44
40
21
21
21
22
23
50
24
14
45
45
40
49
48
46
50
50
50
50
50
50
49
45
50
36
23
17
17
18
12
11
10
50
29
29
20
3
3
3
3
50
30
30
22
1
1
1
2
4
50
25
25
25
25
21
30
30
29
50
18
20
49
47
37
37
37
36
50
9
9
9
5
17
18
14
13
50
26
26
26
28
17
19
...

output:

? 1 50
? 1 30
? 1 18
? 1 11
? 6 11
? 1 5
? 1 3
? 4 5
! 4
? 1 50
? 1 30
? 1 18
? 19 30
? 19 25
? 22 25
? 22 23
? 24 25
! 24
? 1 50
? 21 50
? 33 50
? 21 32
? 21 27
? 21 24
? 21 22
? 23 24
! 24
? 1 50
? 1 30
? 31 50
? 39 50
? 39 45
? 46 50
? 48 50
? 46 47
! 47
? 1 50
? 21 50
? 33 50
? 40 50
? 45 50
? 4...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 203ms
memory: 15592kb

input:

10000
100
76
49
35
34
5
3
11
11
11
100
29
29
29
29
29
29
29
27
26
100
64
64
69
88
88
86
78
77
81
100
51
57
98
98
92
79
79
77
81
100
44
44
50
13
13
13
12
9
9
100
64
92
22
19
27
25
35
36
39
100
93
93
86
56
59
40
44
49
48
47
100
37
2
97
81
76
76
74
68
68
100
76
76
58
94
95
80
79
86
85
83
100
32
32
11
5...

output:

? 1 100
? 40 100
? 1 39
? 16 39
? 1 15
? 1 9
? 10 15
? 10 13
? 10 11
! 10
? 1 100
? 1 61
? 1 37
? 16 37
? 25 37
? 25 32
? 25 29
? 27 29
? 25 26
! 25
? 1 100
? 40 100
? 40 76
? 77 100
? 77 90
? 83 90
? 77 82
? 77 80
? 81 82
! 82
? 1 100
? 1 61
? 62 100
? 77 100
? 87 100
? 77 86
? 77 82
? 77 80
? 81 8...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 89ms
memory: 15656kb

input:

1000
1000
475
426
728
728
747
831
831
828
841
841
844
847
847
847
1000
278
17
974
811
766
757
637
637
637
637
639
640
641
643
1000
75
128
871
985
644
686
713
713
732
735
735
737
739
738
1000
239
239
45
577
607
432
442
458
458
458
459
460
462
463
1000
978
978
978
978
978
978
997
914
914
920
923
923
9...

output:

? 1 1000
? 1 624
? 625 1000
? 625 858
? 625 769
? 770 858
? 804 858
? 804 837
? 838 858
? 838 850
? 838 845
? 846 850
? 846 848
? 846 847
! 846
? 1 1000
? 1 624
? 625 1000
? 767 1000
? 625 766
? 679 766
? 625 678
? 625 657
? 625 644
? 633 644
? 633 639
? 640 644
? 640 642
? 643 644
! 644
? 1 1000
? ...

result:

ok Correct (1000 test cases)

Test #9:

score: 0
Accepted
time: 105ms
memory: 15636kb

input:

1017
272
246
111
27
52
73
73
73
73
73
71
75
114
105
91
2
2
2
2
2
2
2
910
173
173
173
173
127
14
14
29
35
37
51
51
51
50
726
229
229
229
201
63
63
28
17
17
13
24
21
26
861
315
104
671
671
688
593
593
593
593
593
593
590
594
1984
133
133
133
406
571
512
724
704
688
673
650
650
650
650
651
649
1145
988...

output:

? 1 272
? 104 272
? 1 103
? 1 64
? 65 103
? 65 88
? 65 78
? 71 78
? 71 75
? 71 73
? 74 75
! 74
? 1 114
? 45 114
? 1 44
? 1 27
? 1 16
? 1 10
? 1 6
? 1 4
? 1 2
! 1
? 1 910
? 1 568
? 1 354
? 1 220
? 85 220
? 1 84
? 1 51
? 1 31
? 32 51
? 32 43
? 44 51
? 47 51
? 49 51
? 50 51
! 49
? 1 726
? 1 453
? 1 282...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 85ms
memory: 15632kb

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43242
43242
43242
43245
43268
43268
43263
43273
43273
43274
43272
100000
32066
54928
68197
71764
88585
88585
88585
86972
89959
89772
90979
90917
91257
91159
91415
91410
91325
91339
91348
91348
91343
91349
91350
913...

output:

? 1 100000
? 1 62499
? 1 39061
? 39062 62499
? 39062 53709
? 39062 48215
? 39062 44781
? 41208 44781
? 42549 44781
? 42549 43943
? 43073 43943
? 43073 43616
? 43278 43616
? 43073 43277
? 43151 43277
? 43199 43277
? 43199 43247
? 43248 43277
? 43260 43277
? 43260 43270
? 43271 43277
? 43271 43274
? 4...

result:

ok Correct (10 test cases)

Test #11:

score: 0
Accepted
time: 81ms
memory: 15688kb

input:

21
84335
47947
47947
22445
9296
1509
17079
17079
17079
17079
17079
17079
16903
17217
17221
17316
17316
17316
17316
17308
17320
17320
17318
17323
159962
128177
145530
35270
7423
54814
49869
40850
38954
43214
43214
43214
43231
43550
43550
43489
43675
43675
43670
43695
43695
43695
43695
43695
43694
436...

output:

? 1 84335
? 1 52709
? 19768 52709
? 1 19767
? 1 12354
? 12355 19767
? 15136 19767
? 15136 18029
? 16222 18029
? 16222 17350
? 16646 17350
? 16646 17085
? 17086 17350
? 17086 17250
? 17251 17350
? 17290 17350
? 17290 17326
? 17305 17326
? 17305 17317
? 17318 17326
? 17318 17323
? 17318 17321
? 17322 ...

result:

ok Correct (21 test cases)

Test #12:

score: 0
Accepted
time: 93ms
memory: 15564kb

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
783270
786055
794273
790964
797591
797591
797591
797591
797468
797004
797004
796975
796850
796850
796844
796864
796864
796864
796864
796864
796865
796863

output:

? 1 1000000
? 375002 1000000
? 375002 765625
? 765626 1000000
? 765626 912109
? 765626 857176
? 765626 822844
? 765626 800994
? 765626 787487
? 787488 800994
? 787488 795848
? 795849 800994
? 795849 799022
? 795849 797806
? 796600 797806
? 797053 797806
? 796600 797052
? 796771 797052
? 796878 79705...

result:

ok Correct (1 test case)

Test #13:

score: 0
Accepted
time: 96ms
memory: 15568kb

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
229707
227478
225790
225790
225790
225790
225611
225474
225474
225483
225407
225407
225417
225419
225419
225421
225423
8676
6498
6498
6498
6498
5867
4978
4978
4731
4684
4684
4684
4676
4692
4692
4692
4690
4693
4693
221085
172303
209705...

output:

? 1 232936
? 87353 232936
? 141948 232936
? 176070 232936
? 197841 232936
? 211278 232936
? 219571 232936
? 224584 232936
? 224584 229745
? 226552 229745
? 224584 226551
? 224584 225800
? 225049 225800
? 225335 225800
? 225513 225800
? 225335 225512
? 225403 225512
? 225445 225512
? 225403 225444
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 111ms
memory: 15640kb

input:

1994
667
666
667
251
250
95
94
36
35
15
14
6
5
2
374
373
374
141
140
54
53
21
20
8
7
3
2
488
486
488
184
183
70
69
27
26
11
10
5
4
2
922
921
922
347
346
131
130
50
49
20
19
8
7
3
2
639
637
639
240
239
91
90
35
34
14
13
6
5
2
353
350
353
133
132
51
50
20
19
8
7
3
2
71
66
71
27
26
11
10
5
4
2
24
21
24...

output:

? 1 667
? 252 667
? 1 251
? 96 251
? 1 95
? 37 95
? 1 36
? 16 36
? 1 15
? 7 15
? 1 6
? 3 6
? 1 2
! 1
? 1 374
? 142 374
? 1 141
? 55 141
? 1 54
? 22 54
? 1 21
? 9 21
? 1 8
? 4 8
? 1 3
? 2 3
! 1
? 1 488
? 185 488
? 1 184
? 71 184
? 1 70
? 28 70
? 1 27
? 12 27
? 1 11
? 6 11
? 1 5
? 3 5
? 1 2
! 1
? 1 92...

result:

ok Correct (1994 test cases)

Test #15:

score: 0
Accepted
time: 78ms
memory: 15520kb

input:

18
153667
153667
153666
57626
57625
22062
22061
8447
8446
3234
3233
1240
1239
476
475
180
179
69
68
27
26
11
10
5
4
2
211376
211374
211376
79267
79266
29726
29725
11148
11147
4182
4181
1569
1568
589
588
222
221
84
83
33
32
13
12
5
4
2
195330
195326
195330
73250
73249
27470
27469
10302
10301
3864
386...

output:

? 1 153667
? 57627 153667
? 1 57626
? 22063 57626
? 1 22062
? 8448 22062
? 1 8447
? 3235 8447
? 1 3234
? 1241 3234
? 1 1240
? 477 1240
? 1 476
? 181 476
? 1 180
? 70 180
? 1 69
? 28 69
? 1 27
? 12 27
? 1 11
? 6 11
? 1 5
? 3 5
? 1 2
! 1
? 1 211376
? 79268 211376
? 1 79267
? 29727 79267
? 1 29726
? 11...

result:

ok Correct (18 test cases)

Test #16:

score: 0
Accepted
time: 108ms
memory: 15624kb

input:

1
1000000
999998
1000000
375001
375000
140626
140625
52736
52735
19777
19776
7417
7416
2782
2781
1044
1043
393
392
148
147
57
56
22
21
9
8
3
2

output:

? 1 1000000
? 375002 1000000
? 1 375001
? 140627 375001
? 1 140626
? 52737 140626
? 1 52736
? 19778 52736
? 1 19777
? 7418 19777
? 1 7417
? 2783 7417
? 1 2782
? 1045 2782
? 1 1044
? 394 1044
? 1 393
? 149 393
? 1 148
? 58 148
? 1 57
? 23 57
? 1 22
? 10 22
? 1 9
? 4 9
? 1 3
? 2 3
! 1

result:

ok Correct (1 test case)

Test #17:

score: 0
Accepted
time: 102ms
memory: 15520kb

input:

1994
667
666
454
27
27
27
27
27
28
2
2
2
2
2
374
372
224
91
96
29
29
16
12
8
5
3
2
488
485
370
161
156
44
58
15
15
14
6
3
2
922
921
662
40
40
40
40
40
51
18
12
7
8
3
2
639
639
421
215
147
68
72
2
2
2
2
2
2
2
353
351
200
91
81
27
27
22
2
2
2
2
71
71
47
6
6
6
6
3
2
24
22
24
7
9
2
2
567
563
332
205
156...

output:

? 1 667
? 252 667
? 1 251
? 1 156
? 1 96
? 1 59
? 1 36
? 16 36
? 1 15
? 1 9
? 1 6
? 1 4
? 1 2
! 1
? 1 374
? 142 374
? 1 141
? 55 141
? 1 54
? 1 33
? 14 33
? 1 13
? 6 13
? 1 5
? 3 5
? 1 2
! 1
? 1 488
? 185 488
? 1 184
? 71 184
? 1 70
? 28 70
? 1 27
? 1 16
? 7 16
? 1 6
? 3 6
? 1 2
! 1
? 1 922
? 348 92...

result:

ok Correct (1994 test cases)

Test #18:

score: 0
Accepted
time: 88ms
memory: 15528kb

input:

18
153667
153667
65961
50668
47562
8350
8350
8350
5820
1644
1644
1499
306
306
198
24
24
24
24
24
16
7
9
3
4
2
211376
211375
91641
67652
36438
4235
4235
4235
4235
4235
3075
973
973
961
221
221
163
79
60
10
10
10
8
2
2
2
195330
195325
161600
36944
36944
17928
1018
1018
1018
1018
1018
1018
1018
923
281...

output:

? 1 153667
? 57627 153667
? 1 57626
? 22063 57626
? 1 22062
? 1 13615
? 1 8402
? 3219 8402
? 1 3218
? 1 1984
? 758 1984
? 1 757
? 1 467
? 179 467
? 1 178
? 1 110
? 1 68
? 1 42
? 1 26
? 11 26
? 1 10
? 5 10
? 1 4
? 3 4
? 1 2
! 1
? 1 211376
? 79268 211376
? 1 79267
? 29727 79267
? 1 29726
? 1 18578
? 1...

result:

ok Correct (18 test cases)

Test #19:

score: 0
Accepted
time: 105ms
memory: 15716kb

input:

1
1000000
999998
783271
169408
169408
188270
8002
8002
8002
8002
8002
8002
6079
1522
1522
1781
42
42
42
42
42
42
42
18
13
15
4
4
3
2

output:

? 1 1000000
? 375002 1000000
? 1 375001
? 1 234375
? 87892 234375
? 1 87891
? 1 54931
? 1 34331
? 1 21456
? 1 13409
? 1 8275
? 3170 8275
? 1 3169
? 1 1955
? 751 1955
? 1 750
? 1 462
? 1 288
? 1 178
? 1 110
? 1 68
? 1 42
? 17 42
? 1 16
? 7 16
? 1 6
? 1 4
? 3 4
? 1 2
! 1

result:

ok Correct (1 test case)

Test #20:

score: 0
Accepted
time: 108ms
memory: 15712kb

input:

1
999999
260772
507886
955966
996647
730076
730076
730076
730076
717528
706326
706326
706326
705072
702009
702009
702009
701978
701488
701488
701453
701361
701361
701361
701361
701361
701361
701359
701358

output:

? 1 999999
? 1 624999
? 625000 999999
? 765626 999999
? 625000 765625
? 677736 765625
? 677736 732665
? 698336 732665
? 711211 732665
? 698336 711210
? 698336 706381
? 701354 706381
? 703241 706381
? 701354 703240
? 701354 702532
? 701354 702089
? 701631 702089
? 701354 701630
? 701354 701525
? 7014...

result:

ok Correct (1 test case)

Test #21:

score: 0
Accepted
time: 108ms
memory: 15716kb

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
536636
536275
536097
536002
536162
536123
536208
536208
536208
536209
536203
536202
536198

output:

? 1 999998
? 1 624998
? 1 390623
? 390624 624998
? 478515 624998
? 478515 570065
? 512847 570065
? 512847 548215
? 526354 548215
? 526354 539866
? 531515 539866
? 534706 539866
? 534706 537899
? 535926 537899
? 536680 537899
? 535926 536679
? 536214 536679
? 535926 536213
? 535926 536103
? 536104 53...

result:

ok Correct (1 test case)

Test #22:

score: 0
Accepted
time: 108ms
memory: 15564kb

input:

1
999997
339297
339297
355318
613666
489939
413343
417456
471212
473604
453304
453304
453304
453304
453304
453304
453304
453304
453404
453059
453059
453067
453017
453017
453013
453005
453002
453007
453007

output:

? 1 999997
? 1 624997
? 1 390622
? 390623 624997
? 478514 624997
? 390623 478513
? 390623 445553
? 445554 478513
? 457915 478513
? 445554 457914
? 450190 457914
? 450190 455016
? 452001 455016
? 452001 453884
? 452709 453884
? 452709 453442
? 452985 453442
? 453158 453442
? 452985 453157
? 452985 45...

result:

ok Correct (1 test case)

Test #23:

score: 0
Accepted
time: 108ms
memory: 15628kb

input:

1
999996
578161
472988
665875
665875
726172
785834
797735
839217
827932
853100
853969
858027
858027
857481
858782
858873
859300
859300
859300
859300
859303
859239
859239
859239
859239
859237
859235
859234

output:

? 1 999996
? 1 624996
? 624997 999996
? 624997 859370
? 624997 771479
? 771480 859370
? 771480 826410
? 826411 859370
? 826411 847009
? 847010 859370
? 847010 854734
? 854735 859370
? 856475 859370
? 856475 858283
? 858284 859370
? 858284 858962
? 858963 859370
? 859117 859370
? 859213 859370
? 8592...

result:

ok Correct (1 test case)

Test #24:

score: 0
Accepted
time: 99ms
memory: 15656kb

input:

2
500000
114103
114103
98381
290103
281943
220637
207866
237265
236565
224587
226042
228173
227703
227371
227012
226893
226893
226930
226805
226805
226799
226770
226764
226777
226777
226778
226774
500000
313297
313297
313297
285097
246160
246160
238712
217669
217669
217434
222822
223239
225110
22472...

output:

? 1 500000
? 1 312499
? 1 195311
? 195312 312499
? 239259 312499
? 195312 239258
? 195312 222777
? 222778 239258
? 228959 239258
? 222778 228958
? 222778 226639
? 226640 228958
? 227510 228958
? 226640 227509
? 226967 227509
? 226640 226966
? 226763 226966
? 226841 226966
? 226763 226840
? 226763 22...

result:

ok Correct (2 test cases)

Test #25:

score: 0
Accepted
time: 93ms
memory: 15656kb

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
459196
453608
466355
466355
466355
465991
467320
467320
467320
467320
467320
467320
467277
467345
467345
467345
467345
467344
467342
467341
499999
101651
101651
101651
101651
98374
24247
24247
18123
9237
9237
8975
6338
6178
4671
4669
4261
426...

output:

? 1 499999
? 187501 499999
? 304689 499999
? 377931 499999
? 423708 499999
? 452319 499999
? 470200 499999
? 452319 470199
? 452319 463493
? 463494 470199
? 463494 467683
? 465066 467683
? 465066 466700
? 466701 467683
? 467070 467683
? 467070 467452
? 467214 467452
? 467214 467362
? 467271 467362
?...

result:

ok Correct (2 test cases)

Test #26:

score: 0
Accepted
time: 103ms
memory: 15536kb

input:

2
499998
367462
193038
152483
183238
53076
53076
53076
53076
49244
37492
37492
37153
39670
39405
40342
40342
40342
40342
40342
40331
40280
40275
40293
40293
40293
40293
40293
499998
122343
122343
3768
201785
201785
209196
246144
246144
244788
252131
252131
252131
252079
253733
253733
253733
253610
2...

output:

? 1 499998
? 187501 499998
? 1 187500
? 70315 187500
? 1 70314
? 26370 70314
? 26370 53834
? 36670 53834
? 43108 53834
? 36670 43107
? 36670 40692
? 36670 39183
? 39184 40692
? 39184 40125
? 40126 40692
? 40126 40479
? 40126 40345
? 40210 40345
? 40262 40345
? 40295 40345
? 40262 40294
? 40262 40281...

result:

ok Correct (2 test cases)

Test #27:

score: 0
Accepted
time: 104ms
memory: 15688kb

input:

2
499997
274071
274071
274071
302688
167121
159831
135636
135636
135636
135636
135636
133612
132171
132002
133080
133080
132896
132781
132781
132768
132735
132725
132743
132737
132746
132745
132748
499997
242708
242708
242708
310592
160791
117737
177106
177106
172524
164685
164685
164685
164155
1630...

output:

? 1 499997
? 1 312497
? 117188 312497
? 190430 312497
? 117188 190429
? 144655 190429
? 117188 144654
? 127489 144654
? 127489 138216
? 131513 138216
? 131513 135701
? 133085 135701
? 131513 133084
? 131513 132493
? 132494 133084
? 132716 133084
? 132855 133084
? 132716 132854
? 132716 132801
? 1327...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 116ms
memory: 15712kb

input:

10000
2
1
2
2
3
2
1
3
3
3
3
1
2
3
1
1
3
3
2
3
2
2
4
3
3
4
4
4
4
2
1
3
4
2
1
4
4
4
3
1
4
3
4
1
4
3
3
4
4
4
4
2
1
3
4
2
1
4
4
4
3
1
4
3
4
1
4
1
2
3
4
1
2
4
4
1
2
3
4
1
2
4
4
1
1
4
1
1
4
4
3
2
4
3
4
2
4
4
3
2
4
3
4
2
4
2
2
4
2
2
5
4
4
3
5
5
5
5
5
3
2
4
5
3
2
5
5
5
5
4
5
4
4
4
5
4
4
3
5
5
5
5
5
3
2
4
5
...

output:

? 1 2
! 2
? 1 2
! 1
? 1 3
? 1 2
! 3
? 1 3
? 2 3
! 2
? 1 3
? 1 2
! 3
? 1 3
? 1 2
! 2
? 1 3
? 2 3
! 1
? 1 3
? 1 2
! 1
? 1 4
? 3 4
! 4
? 1 4
? 3 4
! 3
? 1 4
? 1 2
? 3 4
! 4
? 1 4
? 1 2
? 3 4
! 3
? 1 4
? 3 4
? 1 2
! 2
? 1 4
? 3 4
? 1 2
! 2
? 1 4
? 3 4
! 4
? 1 4
? 3 4
! 3
? 1 4
? 1 2
? 3 4
! 4
? 1 4
? 1 ...

result:

ok Correct (10000 test cases)

Test #29:

score: 0
Accepted
time: 139ms
memory: 15708kb

input:

10000
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
7
8
2
3
7
6
8
2
3
8
8
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
7
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
3
7
6
8
2
3
8
8
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
7
8
2
3
7
6
8
2
3
8
8
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
7
8
2
3
7
6
8
2
...

output:

? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 1 3
? ...

result:

ok Correct (10000 test cases)

Test #30:

score: 0
Accepted
time: 134ms
memory: 15628kb

input:

10000
8
2
3
7
6
8
2
3
8
8
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
7
8
2
3
7
6
8
2
3
8
8
8
2
3
6
7
8
2
3
6
6
8
2
3
8
7
8
2
3
7
7
8
2
5
7
6
8
2
5
8
8
8
2
5
6
7
8
2
5
6
6
8
2
5
8
7
8
2
5
7
7
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
2
3
4
8
2
4
7
6
8
2
4
8
8
8
2
4
6
7
8
2
4
6
6
8
2
4
8
7
8
2
...

output:

? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? ...

result:

ok Correct (10000 test cases)

Test #31:

score: 0
Accepted
time: 136ms
memory: 15712kb

input:

10000
8
2
4
8
7
8
2
4
7
7
8
2
2
1
4
8
2
2
1
4
8
2
2
1
4
8
2
2
1
4
8
2
2
1
4
8
2
2
1
4
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
2
1
5
8
2
...

output:

? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 5
? 1 8
? 1 5
? 1 3
? 4 5
! 4
? 1 8
? 1 5
? 1 3
? 4 5
! 4
? 1 8
? 1 5
? 1 3
? ...

result:

ok Correct (10000 test cases)

Test #32:

score: 0
Accepted
time: 162ms
memory: 15684kb

input:

10000
8
1
2
6
7
8
1
2
6
6
8
1
2
8
7
8
1
2
7
7
8
1
2
7
6
8
1
2
8
8
8
1
2
6
7
8
1
2
6
6
8
1
2
8
7
8
1
2
7
7
8
1
1
2
4
8
1
1
2
4
8
1
1
2
4
8
1
1
2
4
8
1
1
2
4
8
1
1
2
4
8
1
2
7
6
8
1
2
8
8
8
1
2
6
7
8
1
2
6
6
8
1
2
8
7
8
1
2
7
7
8
1
2
7
6
8
1
2
8
8
8
1
2
6
7
8
1
2
6
6
8
1
2
8
7
8
1
2
7
7
8
1
2
7
6
8
1
...

output:

? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 7 8
! 7
? 1 8
? 1 5
? 6 8
? 6 7
! 8
? 1 8
? 1 5
? 6 8
? 6 7
! 7
? 1 8
? 1 5
? 6 8
? 7 8
! 6
? 1 8
? 1 5
? 6 8
? 6 7
! 6
? 1 8
? 1 5
? 1 3
? ...

result:

ok Correct (10000 test cases)

Test #33:

score: 0
Accepted
time: 104ms
memory: 15716kb

input:

10000
9
3
5
8
7
9
3
5
9
9
9
3
5
7
8
9
3
5
7
7
9
3
5
9
8
9
3
5
8
8
9
3
5
8
7
9
3
5
9
9
9
3
5
7
8
9
3
5
7
7
9
3
5
9
8
9
3
5
8
8
9
3
6
8
7
9
3
6
9
9
9
3
6
7
8
9
3
6
7
7
9
3
6
9
8
9
3
6
8
8
9
3
3
4
5
9
3
3
4
5
9
3
3
4
5
9
3
3
4
5
9
3
3
4
5
9
3
3
4
5
9
3
5
8
7
9
3
5
9
9
9
3
5
7
8
9
3
5
7
7
9
3
5
9
8
9
3
...

output:

? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 8 9
! 8
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 8 9
! 8
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? ...

result:

ok Correct (10000 test cases)

Test #34:

score: 0
Accepted
time: 148ms
memory: 15524kb

input:

10000
9
3
5
9
8
9
3
5
8
8
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
3
2
6
9
3
...

output:

? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #35:

score: 0
Accepted
time: 144ms
memory: 15568kb

input:

10000
9
3
2
7
8
9
3
2
7
7
9
3
2
9
8
9
3
2
8
8
9
3
6
8
7
9
3
6
9
9
9
3
6
7
8
9
3
6
7
7
9
3
6
9
8
9
3
6
8
8
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
3
2
5
9
3
2
8
7
9
3
2
9
9
9
3
2
7
8
9
3
2
7
7
9
3
2
9
8
9
3
2
8
8
9
3
2
8
7
9
3
2
9
9
9
3
2
7
8
9
3
2
7
7
9
3
2
9
8
9
3
2
8
8
9
3
6
8
7
9
3
...

output:

? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 8 9
! 8
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #36:

score: 0
Accepted
time: 135ms
memory: 15688kb

input:

10000
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
2
1
3
9
2
2
...

output:

? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 4
! 4
? 1 9
? 1 6
? 1 4
? 1 2
? 3 ...

result:

ok Correct (10000 test cases)

Test #37:

score: 0
Accepted
time: 130ms
memory: 15640kb

input:

10000
9
4
3
9
8
9
4
3
8
8
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
...

output:

? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 126ms
memory: 15712kb

input:

10000
9
4
3
7
8
9
4
3
7
7
9
4
3
9
8
9
4
3
8
8
9
4
3
8
7
9
4
3
9
9
9
4
3
7
8
9
4
3
7
7
9
4
3
9
8
9
4
3
8
8
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
3
8
7
9
4
3
9
9
9
4
3
7
8
9
4
3
7
7
9
4
3
9
8
9
4
3
8
8
9
4
3
8
7
9
4
3
9
9
9
4
3
7
8
9
4
3
7
7
9
4
3
9
8
9
4
3
8
8
9
4
3
8
7
9
4
...

output:

? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 8 9
! 8
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #39:

score: 0
Accepted
time: 161ms
memory: 15568kb

input:

10000
9
8
8
8
8
9
9
9
9
9
9
7
7
4
8
9
7
7
4
9
9
9
9
9
8
6
9
8
8
8
9
6
9
8
8
8
8
9
9
9
9
9
9
7
7
4
8
9
7
7
4
9
9
9
9
9
8
6
9
8
8
8
9
6
9
6
3
8
7
9
6
3
9
9
9
6
3
7
8
9
6
3
7
7
9
6
3
9
8
9
6
3
8
8
9
9
9
9
8
7
9
8
8
8
9
7
9
9
9
9
8
7
9
8
8
8
9
7
9
7
7
7
7
9
7
7
7
7
9
5
3
8
7
9
5
3
9
9
9
5
3
7
8
9
5
3
7
...

output:

? 1 9
? 4 9
? 6 9
? 8 9
! 9
? 1 9
? 4 9
? 6 9
? 8 9
! 8
? 1 9
? 4 9
? 4 7
? 8 9
! 9
? 1 9
? 4 9
? 4 7
? 8 9
! 8
? 1 9
? 4 9
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 4 9
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 4 9
? 6 9
? 8 9
! 9
? 1 9
? 4 9
? 6 9
? 8 9
! 8
? 1 9
? 4 9
? 4 7
? 8 9
! 9
? 1 9
? 4 9
? 4 7
? 8 9
! 8
? 1 9
? ...

result:

ok Correct (10000 test cases)

Test #40:

score: 0
Accepted
time: 138ms
memory: 15640kb

input:

10000
9
2
5
9
8
9
2
5
8
8
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
2
3
6
9
2
...

output:

? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #41:

score: 0
Accepted
time: 144ms
memory: 15716kb

input:

10000
9
7
7
6
8
9
7
7
6
9
9
9
9
9
8
6
9
8
8
8
9
6
9
6
3
8
7
9
6
3
9
9
9
6
3
7
8
9
6
3
7
7
9
6
3
9
8
9
6
3
8
8
9
9
9
9
8
7
9
8
8
8
9
7
9
9
9
9
8
7
9
8
8
8
9
7
9
7
7
7
7
9
7
7
7
7
9
8
8
8
8
9
9
9
9
9
9
7
7
4
8
9
7
7
4
9
9
9
9
9
8
6
9
8
8
8
9
6
9
8
8
8
8
9
9
9
9
9
9
7
7
6
8
9
7
7
6
9
9
9
9
9
8
6
9
8
8
...

output:

? 1 9
? 4 9
? 4 7
? 8 9
! 9
? 1 9
? 4 9
? 4 7
? 8 9
! 8
? 1 9
? 4 9
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 4 9
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 8 9
! 8
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? ...

result:

ok Correct (10000 test cases)

Test #42:

score: 0
Accepted
time: 163ms
memory: 15628kb

input:

10000
9
8
8
8
8
9
9
9
9
9
9
7
7
5
8
9
7
7
5
9
9
9
9
9
8
6
9
8
8
8
9
6
9
8
8
8
8
9
9
9
9
9
9
7
7
5
8
9
7
7
5
9
9
9
9
9
8
6
9
8
8
8
9
6
9
6
3
8
7
9
6
3
9
9
9
6
3
7
8
9
6
3
7
7
9
6
3
9
8
9
6
3
8
8
9
9
9
9
8
7
9
8
8
8
9
7
9
9
9
9
8
7
9
8
8
8
9
7
9
7
7
7
7
9
7
7
7
7
9
5
3
8
7
9
5
3
9
9
9
5
3
7
8
9
5
3
7
...

output:

? 1 9
? 4 9
? 6 9
? 8 9
! 9
? 1 9
? 4 9
? 6 9
? 8 9
! 8
? 1 9
? 4 9
? 4 7
? 8 9
! 9
? 1 9
? 4 9
? 4 7
? 8 9
! 8
? 1 9
? 4 9
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 4 9
? 6 9
? 8 9
? 6 7
! 7
? 1 9
? 4 9
? 6 9
? 8 9
! 9
? 1 9
? 4 9
? 6 9
? 8 9
! 8
? 1 9
? 4 9
? 4 7
? 8 9
! 9
? 1 9
? 4 9
? 4 7
? 8 9
! 8
? 1 9
? ...

result:

ok Correct (10000 test cases)

Test #43:

score: 0
Accepted
time: 141ms
memory: 15636kb

input:

10000
9
5
3
9
8
9
5
3
8
8
9
5
5
5
5
9
5
5
5
5
9
5
5
5
5
9
5
5
5
5
9
5
5
5
5
9
5
5
5
5
9
9
9
8
4
9
8
8
9
4
9
9
9
7
4
9
8
8
7
4
9
7
7
7
6
4
9
7
7
7
6
4
9
9
9
8
4
9
8
8
9
4
9
9
9
7
4
9
8
8
7
4
9
7
7
7
6
4
9
7
7
7
6
4
9
9
9
6
4
9
8
8
6
4
9
9
9
6
4
9
8
8
6
4
9
7
7
7
6
4
9
7
7
7
6
4
9
6
6
6
6
9
6
6
6
6
9
...

output:

? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 3 6
? 5 6
! 6
? 1 9
? 1 6
? 3 6
? 5 6
! 6
? 1 9
? 1 6
? 3 6
? 5 6
! 6
? 1 9
? 1 6
? 3 6
? 5 6
! 6
? 1 9
? 1 6
? 3 6
? 5 6
! 6
? 1 9
? 1 6
? 3 6
? 5 6
! 6
? 1 9
? 4 9
? 6 9
? 4 5
! 5
? 1 9
? 4 9
? 6 9
? 4 5
! 5
? 1 9
? 4 9
? 6 9
? ...

result:

ok Correct (10000 test cases)

Test #44:

score: 0
Accepted
time: 164ms
memory: 15644kb

input:

10000
9
2
3
7
8
9
2
3
7
7
9
2
3
9
8
9
2
3
8
8
9
2
6
8
7
9
2
6
9
9
9
2
6
7
8
9
2
6
7
7
9
2
6
9
8
9
2
6
8
8
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
2
3
5
9
2
3
8
7
9
2
3
9
9
9
2
3
7
8
9
2
3
7
7
9
2
3
9
8
9
2
3
8
8
9
2
3
8
7
9
2
3
9
9
9
2
3
7
8
9
2
3
7
7
9
2
3
9
8
9
2
3
8
8
9
2
6
8
7
9
2
...

output:

? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 8 9
! 8
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #45:

score: 0
Accepted
time: 146ms
memory: 15632kb

input:

10000
9
9
9
8
5
9
8
8
9
5
9
9
9
7
5
9
8
8
7
5
9
7
7
7
6
5
9
7
7
7
6
5
9
9
9
8
5
9
8
8
9
5
9
9
9
7
5
9
8
8
7
5
9
7
7
7
6
5
9
7
7
7
6
5
9
9
9
6
5
9
8
8
6
5
9
9
9
6
5
9
8
8
6
5
9
7
7
7
6
5
9
7
7
7
6
5
9
6
6
6
5
3
9
6
6
6
5
3
9
6
6
6
5
3
9
6
6
6
5
3
9
6
6
6
5
3
9
6
6
6
5
3
9
9
9
8
5
9
8
8
9
5
9
9
9
7
5
...

output:

? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 4 7
? 6 7
? 4 5
! 4
? 1 9
? 4 9
? 4 7
? 6 7
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? 4 9
? 6 9
? 4 5
! 4
? 1 9
? ...

result:

ok Correct (10000 test cases)

Test #46:

score: 0
Accepted
time: 144ms
memory: 15528kb

input:

10000
9
4
5
9
8
9
4
5
8
8
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
5
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
4
3
6
9
4
...

output:

? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 6
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? 5 6
! 5
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Test #47:

score: 0
Accepted
time: 161ms
memory: 15568kb

input:

10000
9
4
2
7
8
9
4
2
7
7
9
4
2
9
8
9
4
2
8
8
9
4
6
8
7
9
4
6
9
9
9
4
6
7
8
9
4
6
7
7
9
4
6
9
8
9
4
6
8
8
9
4
4
2
5
9
4
4
2
5
9
4
4
2
5
9
4
4
2
5
9
4
4
2
5
9
4
4
2
5
9
4
2
8
7
9
4
2
9
9
9
4
2
7
8
9
4
2
7
7
9
4
2
9
8
9
4
2
8
8
9
4
2
8
7
9
4
2
9
9
9
4
2
7
8
9
4
2
7
7
9
4
2
9
8
9
4
2
8
8
9
4
6
8
7
9
4
...

output:

? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 8 9
! 8
? 1 9
? 1 6
? 7 9
? 7 8
! 9
? 1 9
? 1 6
? 7 9
? 7 8
! 8
? 1 9
? 1 6
? 7 9
? 8 9
! 7
? 1 9
? 1 6
? 7 9
? 7 8
! 7
? 1 9
? 1 6
? 1 4
? ...

result:

ok Correct (10000 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-08 17:07:53 | OpenSource Project