Points on a Line
This is an interactive problem.
There are points on a number line with integer coordinates . It is guaranteed that for .
A point is considered to be between points and if and only if it belongs to the segment constructed on points and . Formally, point is between points and if and only if or .
You need to find any two indices and such that all points are between points and .
You can use the following query: select three indices (, , ) and find out if point is between points and .
You are allowed to use no more than queries.
It is guaranteed that the coordinates of the points are fixed before the interaction begins. In other words, the interactor is not adaptive.
Input
The first line contains a single integer () — the number of points.
Interaction
To make a query, output "?
" (), then output a newline character and perform the flush
operation.
In response to the query, the jury program will output a single integer (). If , then point is between points and ; if , then point is not between them.
If the query is invalid (i.e., the maximum number of queries is exceeded or the query parameters are invalid), the jury program will output -1
and terminate. In this case, terminate the program to receive the verdict Wrong Answer
.
When you are ready to provide an answer, output it in the format "!
" (), where and are the sought indices of points. After that, terminate the program.
The flush
operation is performed as follows:
fflush(stdout)
orcout.flush()
inC++
;System.out.flush()
inJava
;flush(output)
inPascal
;sys.stdout.flush()
inPython
.
Examples
4 1 1
? 1 4 2 ? 1 4 3 ! 1 4
Note
In the example, the points have coordinates .
Scoring
( points): ;
( points): ;
( points): ;
( points): , ;
( points): ;
( points): without additional constraints.