Problem Statement

This is an interactive problem.

There is a deck of $N$ stacked cards, where $N$ is even. The cards in the deck are facing up or down in no particular order, but it is known that in total $N/2$ cards (exactly half) are face up.

By asking questions of the format below any number of times, up to $20$ times, find one

• group of consecutive cards in the deck, consisting of "at least $N/2$ and less than $N$" cards, in which the number of face-up cards equals the number of face-down cards

It can be shown that a group satisfying the condition always exists under the constraints of this problem.

[Question format]
Freely choose, each time, any integer $K$ satisfying $1\leq K\leq N$, and ask for "the number of face-up cards among the cards from the top of the deck down to the $K$-th card".

Constraints

• $4\leq N\leq 2\times 10^5$
• $N$ is even
• All inputs are integers

Input and Output

Initial input

$N$

Output when asking a question

$?$ $K$

It must hold that $1\leq K\leq N$, and you may ask at most $20$ questions per test case.

Input of the response to a question

$S$

Here, $S$ is "the number of face-up cards among the cards from the top of the deck down to the $K$-th card" for the queried $K$. If a question is invalid or the number of questions exceeds $20$, $-1$ is given as input. In this case, terminate your program immediately.

Output when giving your answer

$!$ $L$ $R$

When you have determined that the group of cards from the $L$-th to the $R$-th from the top of the deck (both ends inclusive) satisfies the condition, answer as shown above. Here, it must hold that $1\leq L \leq R\leq N$.

Flush after every output. Otherwise, the judge result is undefined. Also, separate each symbol and number with a space.

Sample I/O code (C++ / Python / C): click to expand

C++

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

int main() {
    //入力
    int N; cin >> N;
    
    //質問
    int K = N,S;
    cout << "? " << K << endl;
    cin >> S;
    
    //回答
    int L = 1,R = N;
    cout << "! " << L << " " << R << endl;
}

Python

import sys

##入力
N = int(input())

##質問
K = N
print("? {}".format(K))
sys.stdout.flush()
S = int(input())

##回答
L = 1; R = N
print("! {} {}".format(L,R))
sys.stdout.flush()

C

#include <stdio.h>

int main(){
    //入力
    int N;
    scanf("%d", &N);
	
    //質問
    int K = N,S;
    printf("? %d\n", K);
    fflush(stdout);
    scanf("%d", &S);
	
    //回答
    int L = 1,R = N;
    printf("! %d %d\n", L, R);
    fflush(stdout);
}

Sample