QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607532#8939. PermutationUESTC_DECAYALIAC ✓142ms11852kbC++201.8kb2024-10-03 15:12:292024-10-03 15:12:29

Judging History

This is the latest submission verdict.

  • [2024-10-03 15:12:29]
  • Judged
  • Verdict: AC
  • Time: 142ms
  • Memory: 11852kb
Show
  • [2024-10-03 15:12:29]
  • Submitted

answer

#include<cstdio>
#include<iostream>
#include<cmath>
#include<map>
#include<cassert>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000000;
const double alpha=pow(2.0,2.0/3.0);
const double theta=alpha/(1.0+alpha);
int t,n,cnt,sum,f[N+5],pos[N+5]; map <pair <int,int>,int> rst;
inline int ask(CI l,CI r)
{
    assert(r-l+1>=2);
    if (rst.count({l,r})) return rst[{l,r}];
    printf("? %d %d\n",l,r); fflush(stdout);
    ++cnt; sum+=r-l+1;
    int res; scanf("%d",&res); return rst[{l,r}]=res;
}
inline void answer(CI p)
{
    printf("! %d\n",p); fflush(stdout);
}
int main()
{
    f[1]=0; f[2]=1;
    for (RI i=3;i<=N;++i)
    {
        int st=max(1,(int)(theta*i)-1);
        pos[i]=st; f[i]=max(f[st],f[i-st]+1)+1;
        for (RI j=1;j<=3;++j)
        {
            int y=min(st+j,i-1);
            int tmp=max(f[y],f[i-y]+1)+1;
            if (tmp<=f[i]) f[i]=tmp,pos[i]=y;
        }
    }
    //for (RI i=1;i<=N;++i) assert(f[i]<=(int)ceil(1.5L*log2(i)));
    // for (RI i=3;i<=20;++i) printf("%d %d\n",i,pos[i]);
    for (scanf("%d",&t);t;--t)
    {
        scanf("%d",&n); rst.clear(); cnt=0; sum=0;
        int l=1,r=n;
        while (r-l+1>2)
        {
            int smx=ask(l,r),len=pos[r-l+1];
            if (smx<=l+len-1)
            {
                int tmp=ask(l,l+len-1);
                if (smx==tmp) r=l+len-1; else l+=len;
            } else
            {
                int tmp=ask(r-len+1,r);
                if (smx==tmp) l=r-len+1; else r-=len;
            }
        }
        assert(l<=r);
        if (l==r) answer(l); else
        {
            int tmp=ask(l,r);
            if (tmp==l) answer(r); else answer(l);
        }
        assert(cnt<=(int)ceil(1.5L*log2(n)));
        assert(sum<=3*n);
    }
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 11772kb

input:

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

output:

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

result:

ok Correct (3 test cases)

Test #2:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 76ms
memory: 11784kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 128ms
memory: 11804kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 62ms
memory: 11784kb

input:

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

output:

? 1 100
? 1 63
? 64 100
? 77 100
? 64 76
? 64 71
? 67 71
? 69 71
? 70 71
! 70
? 1 9
? 1 7
? 1 5
? 1 3
? 1 2
! 3
? 1 53
? 20 53
? 1 19
? 1 13
? 1 8
? 4 8
? 4 6
? 5 6
! 5
? 1 33
? 1 21
? 22 33
? 26 33
? 29 33
? 29 31
? 32 33
! 33
? 1 82
? 31 82
? 1 30
? 11 30
? 18 30
? 23 30
? 26 30
? 23 25
? 23 24
! ...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 142ms
memory: 11648kb

input:

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

output:

? 1 50
? 1 32
? 1 21
? 1 13
? 6 13
? 1 5
? 1 3
? 4 5
! 4
? 1 50
? 1 32
? 1 21
? 22 32
? 25 32
? 22 24
? 22 23
! 24
? 1 50
? 19 50
? 30 50
? 19 29
? 19 26
? 19 23
? 24 26
? 25 26
! 24
? 1 50
? 1 32
? 33 50
? 33 45
? 46 50
? 48 50
? 46 47
! 47
? 1 50
? 19 50
? 30 50
? 38 50
? 43 50
? 46 50
? 48 50
? 4...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 120ms
memory: 11776kb

input:

10000
100
76
49
35
34
5
3
9
9
9
100
29
29
29
29
29
29
29
30
26
26
100
64
64
38
88
88
88
88
86
83
83
100
51
57
98
98
92
79
81
84
83
100
44
44
50
13
13
13
13
12
6
7
100
64
64
64
62
41
41
41
41
42
39
100
93
93
86
56
56
59
49
47
45
100
37
2
97
81
76
76
74
70
70
100
76
76
58
94
95
80
79
83
100
32
32
11
5...

output:

? 1 100
? 38 100
? 1 37
? 14 37
? 1 13
? 1 8
? 9 13
? 9 11
? 9 10
! 10
? 1 100
? 1 63
? 1 40
? 15 40
? 15 31
? 20 31
? 24 31
? 27 31
? 24 26
? 25 26
! 25
? 1 100
? 38 100
? 38 77
? 78 100
? 78 93
? 78 88
? 81 88
? 84 88
? 81 83
? 82 83
! 82
? 1 100
? 1 63
? 64 100
? 77 100
? 85 100
? 77 84
? 77 81
?...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 18ms
memory: 11772kb

input:

1000
1000
475
426
728
728
747
831
831
828
841
837
847
847
847
847
1000
278
17
974
811
757
751
637
637
637
639
647
645
642
643
1000
75
128
871
985
644
686
713
713
712
732
730
737
739
741
1000
239
239
45
577
607
432
429
442
451
458
458
459
463
463
1000
978
978
978
978
978
978
997
914
914
920
927
927
9...

output:

? 1 1000
? 1 615
? 616 1000
? 616 853
? 616 763
? 764 853
? 797 853
? 797 832
? 833 853
? 833 845
? 846 853
? 846 850
? 846 848
? 846 847
! 846
? 1 1000
? 1 615
? 616 1000
? 763 1000
? 616 762
? 671 762
? 616 670
? 616 649
? 629 649
? 629 641
? 642 649
? 645 649
? 642 644
? 642 643
! 644
? 1 1000
? ...

result:

ok Correct (1000 test cases)

Test #9:

score: 0
Accepted
time: 28ms
memory: 11836kb

input:

1017
272
246
111
27
52
73
73
73
73
68
77
75
114
105
91
2
2
2
2
2
2
2
2
910
173
173
173
173
127
14
14
29
35
37
51
51
50
726
229
229
229
201
63
63
63
44
28
28
28
28
29
26
861
315
104
671
671
688
593
593
593
593
593
593
590
597
596
1984
133
133
133
406
571
512
724
704
673
674
650
650
650
650
651
647
11...

output:

? 1 272
? 105 272
? 1 104
? 1 65
? 66 104
? 66 90
? 66 82
? 66 77
? 66 73
? 74 77
? 75 77
! 74
? 1 114
? 44 114
? 1 43
? 1 28
? 1 19
? 1 13
? 1 8
? 1 5
? 1 3
? 1 2
! 1
? 1 910
? 1 560
? 1 345
? 1 213
? 82 213
? 1 81
? 1 51
? 1 33
? 34 51
? 34 46
? 47 51
? 49 51
? 50 51
! 49
? 1 726
? 1 447
? 1 276
?...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 20ms
memory: 11804kb

input:

10
100000
3893
3893
30673
43582
43582
43582
43582
43582
43582
43582
43582
43582
43470
43242
43242
43197
43289
43289
43279
43268
43268
43267
43270
100000
32066
54928
68197
71764
88585
88585
85554
93282
94213
91599
91599
91599
91474
91257
91225
91410
91398
91348
91348
91348
91348
91349
91351
91350
100...

output:

? 1 100000
? 1 61353
? 1 37642
? 37643 61353
? 37643 52190
? 37643 46569
? 41092 46569
? 41092 44453
? 42390 44453
? 42390 43657
? 42879 43657
? 43179 43657
? 43363 43657
? 43179 43362
? 43179 43292
? 43179 43249
? 43250 43292
? 43265 43292
? 43274 43292
? 43265 43273
? 43265 43271
? 43265 43269
? 4...

result:

ok Correct (10 test cases)

Test #11:

score: 0
Accepted
time: 18ms
memory: 11652kb

input:

21
84335
47947
47947
22445
9296
1509
19830
19830
19830
19815
17510
17510
17510
17510
17496
17316
17316
17316
17316
17308
17320
17320
17318
17323
159962
128177
145530
35270
7423
54814
49869
40850
38954
46872
46914
43823
43823
43823
43823
43765
43675
43675
43670
43695
43695
43695
43695
43695
43695
436...

output:

? 1 84335
? 1 51742
? 19997 51742
? 1 19996
? 1 12269
? 12270 19996
? 15255 19996
? 17086 19996
? 18210 19996
? 17086 18209
? 17086 17776
? 17086 17510
? 17249 17510
? 17349 17510
? 17249 17348
? 17286 17348
? 17286 17325
? 17300 17325
? 17300 17316
? 17317 17325
? 17317 17323
? 17317 17321
? 17322 ...

result:

ok Correct (21 test cases)

Test #12:

score: 0
Accepted
time: 15ms
memory: 11652kb

input:

1
1000000
641602
641602
418256
783270
783270
783270
783270
786055
805651
805651
802269
797591
797591
797591
797591
797004
796734
796559
796850
796850
796850
796850
796844
796864
796864
796864
796864
796864
796863

output:

? 1 1000000
? 386488 1000000
? 386488 762886
? 762887 1000000
? 762887 908360
? 762887 852138
? 762887 817645
? 762887 796483
? 796484 817645
? 796484 809468
? 801501 809468
? 796484 801500
? 796484 799562
? 796484 798374
? 796484 797645
? 796932 797645
? 796484 796931
? 796484 796759
? 796760 79693...

result:

ok Correct (1 test case)

Test #13:

score: 0
Accepted
time: 20ms
memory: 11808kb

input:

16
232936
229707
229707
229707
229707
229707
229707
229707
229707
229707
227478
225790
225790
225790
225915
225474
225474
225474
225474
225466
225417
225417
225419
225425
225425
225425
8676
6498
6498
6498
6498
5867
4978
4978
5022
4731
4731
4731
4717
4684
4684
4684
4690
4692
4692
4693
221085
172303
2...

output:

? 1 232936
? 90027 232936
? 145259 232936
? 179144 232936
? 199933 232936
? 212687 232936
? 220512 232936
? 225313 232936
? 225313 229991
? 227120 229991
? 225313 227119
? 225313 226422
? 225313 225994
? 225575 225994
? 225313 225574
? 225313 225474
? 225374 225474
? 225412 225474
? 225435 225474
? ...

result:

ok Correct (16 test cases)

Test #14:

score: 0
Accepted
time: 65ms
memory: 11772kb

input:

1994
667
666
667
256
255
97
96
36
35
12
11
4
3
374
373
374
143
142
54
53
20
19
7
6
2
488
486
488
187
186
71
70
26
25
9
8
2
922
921
922
355
354
136
135
51
50
18
17
5
4
2
639
637
639
245
244
93
92
34
33
13
12
5
4
2
353
350
353
135
134
51
50
18
17
5
4
2
71
66
71
26
25
9
8
2
24
21
24
8
7
3
2
567
562
567...

output:

? 1 667
? 257 667
? 1 256
? 98 256
? 1 97
? 37 97
? 1 36
? 13 36
? 1 12
? 5 12
? 1 4
? 2 4
! 1
? 1 374
? 144 374
? 1 143
? 55 143
? 1 54
? 21 54
? 1 20
? 8 20
? 1 7
? 3 7
? 1 2
! 1
? 1 488
? 188 488
? 1 187
? 72 187
? 1 71
? 27 71
? 1 26
? 10 26
? 1 9
? 3 9
? 1 2
! 1
? 1 922
? 356 922
? 1 355
? 137 ...

result:

ok Correct (1994 test cases)

Test #15:

score: 0
Accepted
time: 16ms
memory: 11768kb

input:

18
153667
153667
153666
59389
59388
22952
22951
8869
8868
3426
3425
1323
1322
510
509
196
195
74
73
27
26
9
8
2
211376
211374
211376
81693
81692
31572
31571
12201
12200
4714
4713
1820
1819
702
701
270
269
103
102
38
37
13
12
5
4
2
195330
195326
195330
75491
75490
29175
29174
11274
11273
4356
4355
16...

output:

? 1 153667
? 59390 153667
? 1 59389
? 22953 59389
? 1 22952
? 8870 22952
? 1 8869
? 3427 8869
? 1 3426
? 1324 3426
? 1 1323
? 511 1323
? 1 510
? 197 510
? 1 196
? 75 196
? 1 74
? 28 74
? 1 27
? 10 27
? 1 9
? 3 9
? 1 2
! 1
? 1 211376
? 81694 211376
? 1 81693
? 31573 81693
? 1 31572
? 12202 31572
? 1 ...

result:

ok Correct (18 test cases)

Test #16:

score: 0
Accepted
time: 12ms
memory: 11708kb

input:

1
1000000
999998
1000000
386487
386486
149371
149370
57729
57728
22310
22309
8621
8620
3330
3329
1286
1285
496
495
190
189
72
71
26
25
9
8
2

output:

? 1 1000000
? 386488 1000000
? 1 386487
? 149372 386487
? 1 149371
? 57730 149371
? 1 57729
? 22311 57729
? 1 22310
? 8622 22310
? 1 8621
? 3331 8621
? 1 3330
? 1287 3330
? 1 1286
? 497 1286
? 1 496
? 191 496
? 1 190
? 73 190
? 1 72
? 27 72
? 1 26
? 10 26
? 1 9
? 3 9
? 1 2
! 1

result:

ok Correct (1 test case)

Test #17:

score: 0
Accepted
time: 39ms
memory: 11736kb

input:

1994
667
666
454
27
27
27
27
27
28
2
2
2
2
2
2
374
372
224
91
96
29
29
16
12
8
5
3
2
488
485
370
161
156
44
44
43
15
14
3
3
2
922
921
662
40
40
40
40
40
51
18
12
7
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
2
71
71
47
6
6
6
6
8
3
2
24
22
24
7
4
2
2
567
563
332
205...

output:

? 1 667
? 257 667
? 1 256
? 1 159
? 1 99
? 1 62
? 1 40
? 15 40
? 1 14
? 1 10
? 1 8
? 1 5
? 1 3
? 1 2
! 1
? 1 374
? 144 374
? 1 143
? 55 143
? 1 54
? 1 34
? 14 34
? 1 13
? 6 13
? 1 5
? 3 5
? 1 2
! 1
? 1 488
? 188 488
? 1 187
? 72 187
? 1 71
? 1 45
? 17 45
? 1 16
? 6 16
? 1 5
? 1 3
? 2 3
! 1
? 1 922
?...

result:

ok Correct (1994 test cases)

Test #18:

score: 0
Accepted
time: 17ms
memory: 11852kb

input:

18
153667
153667
65961
50668
47562
8350
8350
8350
5820
1644
1644
1499
306
306
477
24
24
24
24
24
16
7
7
5
3
2
211376
211375
91641
67652
80994
4235
4235
4235
4235
4235
3075
973
973
961
221
221
163
79
60
10
10
10
10
8
2
2
195330
195325
161600
36944
36944
17928
1018
1018
1018
1018
1018
1018
1556
281
28...

output:

? 1 153667
? 59390 153667
? 1 59389
? 22953 59389
? 1 22952
? 1 14083
? 1 8642
? 3340 8642
? 1 3339
? 1 2050
? 792 2050
? 1 791
? 1 487
? 188 487
? 1 187
? 1 116
? 1 73
? 1 46
? 1 30
? 11 30
? 1 10
? 1 8
? 4 8
? 1 3
? 2 3
! 1
? 1 211376
? 81694 211376
? 1 81693
? 31573 81693
? 1 31572
? 1 19371
? 1 ...

result:

ok Correct (18 test cases)

Test #19:

score: 0
Accepted
time: 14ms
memory: 11784kb

input:

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

output:

? 1 1000000
? 386488 1000000
? 1 386487
? 1 237116
? 91642 237116
? 1 91641
? 1 56224
? 1 34496
? 1 21165
? 1 12986
? 5018 12986
? 1 5017
? 1 3079
? 1 1891
? 730 1891
? 1 729
? 1 449
? 1 277
? 1 171
? 1 106
? 1 67
? 1 43
? 16 43
? 1 15
? 5 15
? 1 4
? 2 4
! 1

result:

ok Correct (1 test case)

Test #20:

score: 0
Accepted
time: 13ms
memory: 11836kb

input:

1
999999
260772
507886
955966
996647
730076
730076
751781
706326
706326
706326
706326
705072
701051
701051
701051
700522
701488
701488
701488
701453
701361
701361
701361
701361
701361
701361
701359
701356
701356

output:

? 1 999999
? 1 613513
? 613514 999999
? 762885 999999
? 613514 762884
? 671243 762884
? 706660 762884
? 671243 706659
? 684930 706659
? 693327 706659
? 698479 706659
? 701639 706659
? 698479 701638
? 699699 701638
? 700447 701638
? 700447 701179
? 701180 701638
? 701356 701638
? 701356 701530
? 7014...

result:

ok Correct (1 test case)

Test #21:

score: 0
Accepted
time: 19ms
memory: 11800kb

input:

1
999998
295598
295598
73514
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
537464
536777
535839
535839
536002
536097
536052
536162
536156
536208
536208
536208
536206
536200
536200

output:

? 1 999998
? 1 613512
? 1 376398
? 376399 613512
? 468039 613512
? 468039 557290
? 502532 557290
? 523694 557290
? 523694 544307
? 531660 544307
? 531660 539420
? 534658 539420
? 534658 537581
? 535787 537581
? 536479 537581
? 535787 536478
? 535787 536212
? 535787 536049
? 536050 536212
? 536050 53...

result:

ok Correct (1 test case)

Test #22:

score: 0
Accepted
time: 13ms
memory: 11648kb

input:

1
999997
339297
339297
355318
489939
489939
489939
471212
453304
453304
453304
453304
453304
453304
453304
453304
453304
453304
453247
453059
453059
453067
453017
453017
453017
453017
453013
453007
453007
453007

output:

? 1 999997
? 1 613511
? 1 376398
? 376399 613511
? 376399 521871
? 432621 521871
? 467114 521871
? 432621 467113
? 432621 453783
? 440799 453783
? 445816 453783
? 448894 453783
? 450782 453783
? 451941 453783
? 452652 453783
? 452652 453347
? 452919 453347
? 453083 453347
? 452919 453082
? 452981 45...

result:

ok Correct (1 test case)

Test #23:

score: 0
Accepted
time: 19ms
memory: 11768kb

input:

1
999996
578161
472988
665875
726172
958644
966123
888583
907890
865390
859775
853100
853969
858027
858027
857481
858782
858873
859117
858976
859239
859239
859239
859239
859239
859239
859239
859239
859240
859237

output:

? 1 999996
? 1 613511
? 613512 999996
? 613512 850626
? 850627 999996
? 908355 999996
? 850627 908354
? 872937 908354
? 850627 872936
? 859248 872936
? 850627 859247
? 850627 855917
? 855918 859247
? 857204 859247
? 857204 858459
? 858460 859247
? 858460 858944
? 858945 859247
? 858945 859131
? 8591...

result:

ok Correct (1 test case)

Test #24:

score: 0
Accepted
time: 18ms
memory: 11848kb

input:

2
500000
114103
114103
98381
290103
281943
220637
220637
207866
224587
224587
224587
223621
226042
226572
227012
227012
226893
226739
226739
226728
226759
226760
226770
226770
226772
226777
226776
500000
313297
313297
313297
285097
246160
246160
246160
238712
230101
228136
222822
223239
223884
22472...

output:

? 1 500000
? 1 306757
? 1 188201
? 188202 306757
? 234021 306757
? 188202 234020
? 205909 234020
? 205909 223157
? 223158 234020
? 223158 229823
? 223158 227248
? 223158 225668
? 225669 227248
? 225669 226639
? 226640 227248
? 226640 227014
? 226783 227014
? 226640 226782
? 226694 226782
? 226694 22...

result:

ok Correct (2 test cases)

Test #25:

score: 0
Accepted
time: 15ms
memory: 11716kb

input:

2
499999
493493
493493
493493
493493
493493
493493
487773
471068
471068
471068
471825
468187
468187
467811
467320
467320
467320
467320
467320
467329
467345
467345
467345
467345
467344
467339
467339
499999
101651
101651
101651
101651
98374
24247
24247
18123
9237
9237
8975
6574
6338
4671
4671
4669
426...

output:

? 1 499999
? 193243 499999
? 311799 499999
? 384535 499999
? 429159 499999
? 456537 499999
? 473333 499999
? 456537 473332
? 463027 473332
? 467009 473332
? 469452 473332
? 467009 469451
? 467009 468508
? 467587 468508
? 467009 467586
? 467009 467364
? 467145 467364
? 467229 467364
? 467280 467364
?...

result:

ok Correct (2 test cases)

Test #26:

score: 0
Accepted
time: 19ms
memory: 11736kb

input:

2
499998
367462
261014
193038
152483
53076
53076
53076
53076
49244
46002
42856
40342
40342
40342
40342
40342
40342
40342
40374
40253
40255
40280
40285
40293
40293
40293
40293
499998
122343
122343
3768
201785
201785
209196
246144
244788
252131
252131
252131
251090
253733
253733
253733
253733
253610
2...

output:

? 1 499998
? 193243 499998
? 1 193242
? 74685 193242
? 1 74684
? 28864 74684
? 28864 56976
? 39728 56976
? 46393 56976
? 39728 46392
? 42302 46392
? 39728 42301
? 39728 41308
? 39728 40698
? 40102 40698
? 40102 40469
? 40243 40469
? 40243 40383
? 40296 40383
? 40243 40295
? 40243 40276
? 40277 40295...

result:

ok Correct (2 test cases)

Test #27:

score: 0
Accepted
time: 15ms
memory: 11788kb

input:

2
499997
274071
274071
274071
302688
167121
159831
135636
135636
135636
135636
135636
133612
132171
132171
132002
132428
132543
132679
132661
132735
132725
132750
132750
132750
132752
132746
132745
499997
242708
242708
242708
248273
160791
143467
177106
177106
172524
164685
164685
164685
164685
1641...

output:

? 1 499997
? 1 306756
? 118557 306756
? 191293 306756
? 118557 191292
? 146667 191292
? 118557 146666
? 118557 135803
? 125221 135803
? 129310 135803
? 131818 135803
? 133357 135803
? 131818 133356
? 131818 132763
? 131818 132399
? 132400 132763
? 132400 132624
? 132625 132763
? 132625 132711
? 1327...

result:

ok Correct (2 test cases)

Test #28:

score: 0
Accepted
time: 74ms
memory: 11712kb

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
2
4
4
4
4
4
2
3
4
2
2
1
4
4
4
3
4
3
3
3
4
3
1
4
4
4
4
4
2
1
4
2
2
1
4
4
4
3
4
3
3
3
4
1
3
4
1
1
2
4
1
2
4
1
1
2
4
1
1
1
4
1
1
1
4
4
3
4
3
3
2
4
4
2
4
3
3
2
4
2
2
2
4
2
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
? 1 3
! 4
? 1 4
? 2 4
? 3 4
! 3
? 1 4
? 1 3
! 4
? 1 4
? 1 3
? 1 2
! 3
? 1 4
? 2 4
? 3 4
! 2
? 1 4
? 1 3
? 2 3
! 2
? 1 4
? 1 3
! 4
? 1 4
? 2 4
? 3 4
! 3
? 1 4
? 1 3
! 4
? 1 4
? 1 ...

result:

ok Correct (10000 test cases)

Test #29:

score: 0
Accepted
time: 97ms
memory: 11768kb

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: 47ms
memory: 11740kb

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: 95ms
memory: 11852kb

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: 61ms
memory: 11716kb

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: 74ms
memory: 11768kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #34:

score: 0
Accepted
time: 95ms
memory: 11808kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #35:

score: 0
Accepted
time: 86ms
memory: 11840kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #36:

score: 0
Accepted
time: 70ms
memory: 11696kb

input:

10000
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
2
3
5
9
2
2
...

output:

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

result:

ok Correct (10000 test cases)

Test #37:

score: 0
Accepted
time: 60ms
memory: 11772kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #38:

score: 0
Accepted
time: 83ms
memory: 11784kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #39:

score: 0
Accepted
time: 63ms
memory: 11784kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #40:

score: 0
Accepted
time: 71ms
memory: 11776kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #41:

score: 0
Accepted
time: 84ms
memory: 11788kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #42:

score: 0
Accepted
time: 87ms
memory: 11828kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #43:

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

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #44:

score: 0
Accepted
time: 63ms
memory: 11788kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #45:

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

input:

10000
9
9
9
8
3
9
8
8
9
3
9
9
9
7
3
9
8
8
7
3
9
7
7
7
5
3
9
7
7
7
5
3
9
9
9
8
3
9
8
8
9
3
9
9
9
7
3
9
8
8
7
3
9
7
7
7
5
3
9
7
7
7
5
3
9
9
9
6
3
9
8
8
6
3
9
9
9
6
3
9
8
8
6
3
9
7
7
7
6
3
9
7
7
7
6
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
7
3
9
6
6
6
7
3
9
9
9
5
3
9
8
8
5
3
9
9
9
5
3
...

output:

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

result:

ok Correct (10000 test cases)

Test #46:

score: 0
Accepted
time: 62ms
memory: 11800kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Test #47:

score: 0
Accepted
time: 94ms
memory: 11804kb

input:

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

output:

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

result:

ok Correct (10000 test cases)

Extra Test:

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

Server Time: 2025-02-08 16:47:42 | OpenSource Project