QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#126837#6394. Turn on the LightUNos_maricones#AC ✓4ms3588kbC++201.2kb2023-07-19 04:34:572023-07-19 04:34:59

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 04:34:59]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 3588kb
  • [2023-07-19 04:34:57]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std ;

#define ff    first
#define ss    second
#define pb    push_back

typedef long long    ll;
typedef pair<ll,ll>    ii;
typedef long double    lf;


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll SQ = 320;
const ll N = 3e5+5;
const ll mod = 998244353;
const ll oo = 1e9+5;

int ask (int x) {
  cout << "? " << x << endl;
  cin >> x;
  return x;
}

int main(){
  #ifdef LOCAL
//  freopen("input.txt","r",stdin);
  #endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  int n; cin >> n;
  int l = 1, r = n;

  if (ask(1) == 0) {
    cout << "! " << 1 << endl;
    return 0;
  }

  while (l + 1 < r) {
    int mi = (l + r) / 2;
    int g = ask(mi);
    if (g == 0) {
      l++;
      r = mi - 1;
      if (ask(l) == 0) {
        cout << "! " << l << endl;
        return 0;
      }
    }
    else if (g == 2) {
      l = mi;
      if (ask(r) == 2) {
        cout << "! " << r << endl;
        return 0;
      }
      r--;
    }
    else {
      cout << "! " << mi << endl;
      return 0;
    }
  }
  cout << "! " << r << endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3428kb

input:

3
1
2
2

output:

? 1
? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

10
1
2
1
2
2

output:

? 1
? 5
? 10
? 7
? 9
! 9

result:

ok Correct position at 9

Test #3:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

9
1
2
1
2
2

output:

? 1
? 5
? 9
? 6
? 8
! 8

result:

ok Correct position at 8

Test #4:

score: 0
Accepted
time: 1ms
memory: 3396kb

input:

8
1
2
1
2
2

output:

? 1
? 4
? 8
? 5
? 7
! 7

result:

ok Correct position at 7

Test #5:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

7
1
2
1
1

output:

? 1
? 4
? 7
? 5
! 5

result:

ok Correct position at 5

Test #6:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

6
1
2
1
1

output:

? 1
? 3
? 6
? 4
! 4

result:

ok Correct position at 4

Test #7:

score: 0
Accepted
time: 1ms
memory: 3428kb

input:

5
1
2
2

output:

? 1
? 3
? 5
! 5

result:

ok Correct position at 5

Test #8:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

4
1
2
2

output:

? 1
? 2
? 4
! 4

result:

ok Correct position at 4

Test #9:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

3
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #10:

score: 0
Accepted
time: 1ms
memory: 3420kb

input:

2
1

output:

? 1
! 2

result:

ok Correct position at 2

Test #11:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

score: 0
Accepted
time: 2ms
memory: 3432kb

input:

1000000
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 500000
? 1000000
? 749999
? 999999
? 874998
? 999998
? 937497
? 999997
? 968746
? 999996
? 984370
? 999995
? 992182
? 999994
? 996087
? 999993
? 998039
? 999992
? 999015
? 999991
? 999502
? 999990
? 999745
? 999989
? 999866
? 999988
? 999926
? 999987
? 999956
? 999986
? 999970
? 999985
? 99997...

result:

ok Correct position at 999982

Test #13:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

999999
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992181
? 999993
? 996086
? 999992
? 998038
? 999991
? 999014
? 999990
? 999501
? 999989
? 999744
? 999988
? 999865
? 999987
? 999925
? 999986
? 999955
? 999985
? 999969
? 999984
? 999976...

result:

ok Correct position at 999981

Test #14:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

999998
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992180
? 999992
? 996085
? 999991
? 998037
? 999990
? 999013
? 999989
? 999500
? 999988
? 999743
? 999987
? 999864
? 999986
? 999924
? 999985
? 999954
? 999984
? 999968
? 999983
? 999975...

result:

ok Correct position at 999980

Test #15:

score: 0
Accepted
time: 2ms
memory: 3532kb

input:

999997
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499999
? 999997
? 749997
? 999996
? 874996
? 999995
? 937495
? 999994
? 968744
? 999993
? 984368
? 999992
? 992179
? 999991
? 996084
? 999990
? 998036
? 999989
? 999012
? 999988
? 999499
? 999987
? 999742
? 999986
? 999863
? 999985
? 999923
? 999984
? 999953
? 999983
? 999967
? 999982
? 999974...

result:

ok Correct position at 999979

Test #16:

score: 0
Accepted
time: 2ms
memory: 3424kb

input:

999996
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499998
? 999996
? 749996
? 999995
? 874995
? 999994
? 937494
? 999993
? 968743
? 999992
? 984367
? 999991
? 992178
? 999990
? 996083
? 999989
? 998035
? 999988
? 999011
? 999987
? 999498
? 999986
? 999741
? 999985
? 999862
? 999984
? 999922
? 999983
? 999952
? 999982
? 999966
? 999981
? 999973...

result:

ok Correct position at 999978

Test #17:

score: 0
Accepted
time: 2ms
memory: 3428kb

input:

999995
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499998
? 999995
? 749996
? 999994
? 874994
? 999993
? 937493
? 999992
? 968742
? 999991
? 984366
? 999990
? 992177
? 999989
? 996082
? 999988
? 998034
? 999987
? 999010
? 999986
? 999497
? 999985
? 999740
? 999984
? 999861
? 999983
? 999921
? 999982
? 999951
? 999981
? 999965
? 999980
? 999972...

result:

ok Correct position at 999977

Test #18:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

999994
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499997
? 999994
? 749995
? 999993
? 874993
? 999992
? 937492
? 999991
? 968741
? 999990
? 984365
? 999989
? 992176
? 999988
? 996081
? 999987
? 998033
? 999986
? 999009
? 999985
? 999496
? 999984
? 999739
? 999983
? 999860
? 999982
? 999920
? 999981
? 999950
? 999980
? 999964
? 999979
? 999971...

result:

ok Correct position at 999976

Test #19:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

999993
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499997
? 999993
? 749994
? 999992
? 874992
? 999991
? 937491
? 999990
? 968740
? 999989
? 984364
? 999988
? 992175
? 999987
? 996080
? 999986
? 998032
? 999985
? 999008
? 999984
? 999495
? 999983
? 999738
? 999982
? 999859
? 999981
? 999919
? 999980
? 999949
? 999979
? 999963
? 999978
? 999970...

result:

ok Correct position at 999975

Test #20:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

999992
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499996
? 999992
? 749993
? 999991
? 874991
? 999990
? 937490
? 999989
? 968739
? 999988
? 984363
? 999987
? 992174
? 999986
? 996079
? 999985
? 998031
? 999984
? 999007
? 999983
? 999494
? 999982
? 999737
? 999981
? 999858
? 999980
? 999918
? 999979
? 999948
? 999978
? 999962
? 999977
? 999969...

result:

ok Correct position at 999974

Test #21:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

999991
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499996
? 999991
? 749993
? 999990
? 874991
? 999989
? 937489
? 999988
? 968738
? 999987
? 984362
? 999986
? 992173
? 999985
? 996078
? 999984
? 998030
? 999983
? 999006
? 999982
? 999493
? 999981
? 999736
? 999980
? 999857
? 999979
? 999917
? 999978
? 999947
? 999977
? 999961
? 999976
? 999968...

result:

ok Correct position at 999973

Test #22:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

1000000
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1

output:

? 1
? 500000
? 2
? 250000
? 3
? 125001
? 4
? 62502
? 5
? 31253
? 6
? 15629
? 7
? 7817
? 8
? 3912
? 9
? 1960
? 10
? 984
? 11
? 497
? 12
? 254
? 13
? 133
? 14
? 73
? 15
? 43
! 43

result:

ok Correct position at 43

Test #23:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

999999
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
2
1
0
0

output:

? 1
? 500000
? 2
? 250000
? 3
? 125001
? 4
? 62502
? 5
? 31253
? 6
? 15629
? 7
? 7817
? 8
? 3912
? 9
? 1960
? 10
? 984
? 11
? 497
? 12
? 254
? 13
? 133
? 14
? 73
? 15
? 43
? 72
? 57
? 44
? 50
? 56
? 52
? 51
! 51

result:

ok Correct position at 51

Test #24:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

999998
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
2
1
0
0

output:

? 1
? 499999
? 2
? 250000
? 3
? 125001
? 4
? 62502
? 5
? 31253
? 6
? 15629
? 7
? 7817
? 8
? 3912
? 9
? 1960
? 10
? 984
? 11
? 497
? 12
? 254
? 13
? 133
? 14
? 73
? 15
? 43
? 72
? 57
? 44
? 50
? 56
? 52
? 51
! 51

result:

ok Correct position at 51

Test #25:

score: 0
Accepted
time: 2ms
memory: 3428kb

input:

999997
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
2
1
0
0

output:

? 1
? 499999
? 2
? 250000
? 3
? 125001
? 4
? 62502
? 5
? 31253
? 6
? 15629
? 7
? 7817
? 8
? 3912
? 9
? 1960
? 10
? 984
? 11
? 497
? 12
? 254
? 13
? 133
? 14
? 73
? 15
? 43
? 72
? 57
? 44
? 50
? 56
? 52
? 51
! 51

result:

ok Correct position at 51

Test #26:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

1000000
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
0
1
0
1
2
1
0
1
0
1
2
2

output:

? 1
? 500000
? 1000000
? 749999
? 999999
? 874998
? 999998
? 937497
? 999997
? 968746
? 999996
? 984370
? 999995
? 992182
? 999994
? 996087
? 999993
? 998039
? 999992
? 999015
? 999991
? 999502
? 999990
? 999745
? 999989
? 999866
? 999746
? 999805
? 999747
? 999775
? 999804
? 999789
? 999776
? 99978...

result:

ok Correct position at 999781

Test #27:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

999999
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1

output:

? 1
? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992181
? 999993
? 996086
? 999992
? 998038
? 999991
? 999014
? 999990
? 999501
? 999989
? 999744
? 999988
? 999865
? 999987
? 999925
? 999986
? 999955
? 999985
? 999969
? 999984
? 999976...

result:

ok Correct position at 999980

Test #28:

score: 0
Accepted
time: 3ms
memory: 3532kb

input:

999998
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1

output:

? 1
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992180
? 999992
? 996085
? 999991
? 998037
? 999990
? 999013
? 999989
? 999500
? 999988
? 999743
? 999987
? 999864
? 999986
? 999924
? 999985
? 999954
? 999984
? 999968
? 999983
? 999975...

result:

ok Correct position at 999979

Test #29:

score: 0
Accepted
time: 2ms
memory: 3432kb

input:

999997
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1

output:

? 1
? 499999
? 999997
? 749997
? 999996
? 874996
? 999995
? 937495
? 999994
? 968744
? 999993
? 984368
? 999992
? 992179
? 999991
? 996084
? 999990
? 998036
? 999989
? 999012
? 999988
? 999499
? 999987
? 999742
? 999986
? 999863
? 999985
? 999923
? 999984
? 999953
? 999983
? 999967
? 999982
? 999974...

result:

ok Correct position at 999978

Test #30:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

1000000
1
0
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
0
1
2
1
1

output:

? 1
? 500000
? 2
? 250000
? 499999
? 374999
? 499998
? 437498
? 499997
? 468747
? 499996
? 484371
? 499995
? 492182
? 499994
? 496087
? 499993
? 498039
? 499992
? 499015
? 499991
? 499502
? 499990
? 499745
? 499989
? 499866
? 499988
? 499926
? 499987
? 499956
? 499927
? 499941
? 499955
? 499947
! 49...

result:

ok Correct position at 499947

Test #31:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

999999
1
2
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
2

output:

? 1
? 500000
? 999999
? 749999
? 500001
? 624999
? 500002
? 562500
? 500003
? 531251
? 500004
? 515627
? 500005
? 507815
? 500006
? 503910
? 500007
? 501958
? 500008
? 500982
? 500009
? 500495
? 500010
? 500252
? 500011
? 500131
? 500012
? 500071
? 500013
? 500041
? 500070
! 500070

result:

ok Correct position at 500070

Test #32:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

999998
1
2
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
0
1
0
1
2
2

output:

? 1
? 499999
? 999998
? 749998
? 500000
? 624998
? 500001
? 562499
? 500002
? 531250
? 500003
? 515626
? 500004
? 507814
? 500005
? 503909
? 500006
? 501957
? 500007
? 500981
? 500008
? 500494
? 500009
? 500251
? 500010
? 500130
? 500011
? 500070
? 500129
? 500099
? 500071
? 500084
? 500072
? 500077...

result:

ok Correct position at 500076

Test #33:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

999997
1
0
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
0
1
2
1
2
1
1

output:

? 1
? 499999
? 2
? 250000
? 499998
? 374998
? 499997
? 437497
? 499996
? 468746
? 499995
? 484370
? 499994
? 492181
? 499993
? 496086
? 499992
? 498038
? 499991
? 499014
? 499990
? 499501
? 499989
? 499744
? 499988
? 499865
? 499987
? 499925
? 499986
? 499955
? 499985
? 499969
? 499956
? 499962
? 49...

result:

ok Correct position at 499965

Test #34:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

1000000
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1

output:

? 1
? 500000
? 1000000
? 749999
? 999999
? 874998
? 999998
? 937497
? 999997
? 968746
? 999996
? 984370
? 999995
? 992182
? 999994
? 996087
? 999993
? 998039
? 999992
? 999015
? 999991
? 999502
? 999990
? 999745
? 999989
? 999866
? 999988
? 999926
? 999987
? 999956
? 999986
? 999970
? 999985
? 99997...

result:

ok Correct position at 999981

Test #35:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

999999
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1

output:

? 1
? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992181
? 999993
? 996086
? 999992
? 998038
? 999991
? 999014
? 999990
? 999501
? 999989
? 999744
? 999988
? 999865
? 999987
? 999925
? 999986
? 999955
? 999985
? 999969
? 999984
? 999976...

result:

ok Correct position at 999980

Test #36:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

999998
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1

output:

? 1
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992180
? 999992
? 996085
? 999991
? 998037
? 999990
? 999013
? 999989
? 999500
? 999988
? 999743
? 999987
? 999864
? 999986
? 999924
? 999985
? 999954
? 999984
? 999968
? 999983
? 999975...

result:

ok Correct position at 999979

Test #37:

score: 0
Accepted
time: 4ms
memory: 3428kb

input:

999997
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1

output:

? 1
? 499999
? 999997
? 749997
? 999996
? 874996
? 999995
? 937495
? 999994
? 968744
? 999993
? 984368
? 999992
? 992179
? 999991
? 996084
? 999990
? 998036
? 999989
? 999012
? 999988
? 999499
? 999987
? 999742
? 999986
? 999863
? 999985
? 999923
? 999984
? 999953
? 999983
? 999967
? 999982
? 999974...

result:

ok Correct position at 999978

Test #38:

score: 0
Accepted
time: 3ms
memory: 3412kb

input:

1000000
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 500000
? 1000000
? 749999
? 999999
? 874998
? 999998
? 937497
? 999997
? 968746
? 999996
? 984370
? 999995
? 992182
? 999994
? 996087
? 999993
? 998039
? 999992
? 999015
? 999991
? 999502
? 999990
? 999745
? 999989
? 999866
? 999988
? 999926
? 999987
? 999956
? 999986
? 999970
? 999985
? 99997...

result:

ok Correct position at 999982

Test #39:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

999999
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992181
? 999993
? 996086
? 999992
? 998038
? 999991
? 999014
? 999990
? 999501
? 999989
? 999744
? 999988
? 999865
? 999987
? 999925
? 999986
? 999955
? 999985
? 999969
? 999984
? 999976...

result:

ok Correct position at 999981

Test #40:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

999998
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992180
? 999992
? 996085
? 999991
? 998037
? 999990
? 999013
? 999989
? 999500
? 999988
? 999743
? 999987
? 999864
? 999986
? 999924
? 999985
? 999954
? 999984
? 999968
? 999983
? 999975...

result:

ok Correct position at 999980

Test #41:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

999997
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
2

output:

? 1
? 499999
? 999997
? 749997
? 999996
? 874996
? 999995
? 937495
? 999994
? 968744
? 999993
? 984368
? 999992
? 992179
? 999991
? 996084
? 999990
? 998036
? 999989
? 999012
? 999988
? 999499
? 999987
? 999742
? 999986
? 999863
? 999985
? 999923
? 999984
? 999953
? 999983
? 999967
? 999982
? 999974...

result:

ok Correct position at 999979

Test #42:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

1000000
1
2
2

output:

? 1
? 500000
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

score: 0
Accepted
time: 0ms
memory: 3428kb

input:

1000000
0

output:

? 1
! 1

result:

ok Correct position at 1