Problem: This is an interactive problem.

Homer likes arrays a lot and he wants to play a game with you. 

Homer has hidden from you a permutation a_1, a_2, ..., a_n of integers 1 to n. You are asked to find any index k (1 ≤ k ≤ n) which is a local minimum. 

For an array a_1, a_2, ..., a_n, an index i (1 ≤ i ≤ n) is said to be a local minimum if a_i < min\\{a_{i-1},a_{i+1}\}, where a_0 = a_{n+1} = +∞. An array is said to be a permutation of integers 1 to n, if it contains all integers from 1 to n exactly once.

Initially, you are only given the value of n without any other information about this permutation.

At each interactive step, you are allowed to choose any i (1 ≤ i ≤ n) and make a query with it. As a response, you will be given the value of a_i. 

You are asked to find any index k which is a local minimum after at most 100 queries.

Interaction

You begin the interaction by reading an integer n (1≤ n ≤ 10^5) on a separate line.

To make a query on index i (1 ≤ i ≤ n), you should output "? i" in a separate line. Then read the value of a_i in a separate line. The number of the "?" queries is limited within 100.

When you find an index k (1 ≤ k ≤ n) which is a local minimum, output "! k" in a separate line and terminate your program. 

In case your query format is invalid, or you have made more than 100 "?" queries, you will receive Wrong Answer verdict. 

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Hack Format

The first line of the hack should contain a single integer n (1 ≤ n ≤ 10^5).

The second line should contain n distinct integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

Example

Input


5
3
2
1
4
5


Output


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

Note

In the example, the first line contains an integer 5 indicating that the length of the array is n = 5.

The example makes five "?" queries, after which we conclude that the array is a = [3,2,1,4,5] and k = 3 is local minimum.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.lang.*;
public class Main{
    public static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
     
        public int read() {
            if (numChars==-1)
                throw new InputMismatchException();
     
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
     
                if(numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
     
            while(isSpaceChar(c))
                c = read();
     
            int sgn = 1;
     
            if (c == '-') {
                sgn = -1;
                c = read();
            }
     
            int res = 0;
            do {
                if(c<'0'||c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
     
            return res * sgn;
        }
     
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
     
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }
     
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
     
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));
     
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
     
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
 
    static long gcd(long a, long b){
        if (a == 0)
            return b;  
        return gcd(b % a, a);  
    }
    static long lcm(long a, long b)  {
        return (a*b)/gcd(a, b);  
    }
    public static void sortbyColumn(int arr[][], int col) 
    { 
        
        Arrays.sort(arr, new Comparator<int[]>() { 
            
          @Override              
          
          public int compare(final int[] entry1,  
                             final int[] entry2) { 
  
            
            if (entry1[col] > entry2[col]) 
                return 1; 
            else
                return -1; 
          } 
        });  
    } 
    static long func(long a[],int size,int s){
        long max1=a[s];
        long maxc=a[s];
        for(int i=s+1;i<size;i++){
            maxc=Math.max(a[i],maxc+a[i]);
            max1=Math.max(maxc,max1);
        }
        return max1;
    }
    public static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        public U x;
        public V y;
    
        public Pair(U x, V y) {
            this.x = x;
            this.y = y;
        }
    
        public int hashCode() {
            return (x == null ? 0 : x.hashCode() * 31) + (y == null ? 0 : y.hashCode());
        }
    
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (x == null ? p.x == null : x.equals(p.x)) && (y == null ? p.y == null : y.equals(p.y));
        }
    
        public int compareTo(Pair<U, V> b) {
            int cmpU = x.compareTo(b.x);
            return cmpU != 0 ? cmpU : y.compareTo(b.y);
        }
    
        public String toString() {
            return String.format("(%s, %s)", x.toString(), y.toString());
        }
    
    }
    static class MultiSet<U extends Comparable<U>> {
        public int sz = 0;
        public TreeMap<U, Integer> t;
 
        public MultiSet() {
            t = new TreeMap<>();
        }
 
        public void add(U x) {
            t.put(x, t.getOrDefault(x, 0) + 1);
            sz++;
        }
 
        public void remove(U x) {
            if (t.get(x) == 1) t.remove(x);
            else t.put(x, t.get(x) - 1);
            sz--;
        }
 
    }
    static void shuffle(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    static long myceil(long a, long b){
        return (a+b-1)/b;
    }
    
    static long C(long n,long r){
        long count=0,temp=n;
        long ans=1;
        long num=n-r+1,div=1;
        while(num<=n){
            ans*=num;
            //ans+=MOD;
            ans%=MOD;
            ans*=mypow(div,MOD-2);
            //ans+=MOD;
            ans%=MOD;
            num++;
            div++;
        }
        
        ans+=MOD;
        return ans%MOD;
    }
    static long fact(long a){
        long i,ans=1;
        for(i=1;i<=a;i++){
            ans*=i;
            ans%=MOD;
        }
        return ans%=MOD;
    }
    static void sieve(int n){
        is_sieve[0]=1;
        is_sieve[1]=1;
        int i,j,k;
        for(i=2;i<n;i++){
            if(is_sieve[i]==0){
                sieve[i]=i;
                tr.add(i);
                for(j=i*i;j<n;j+=i){
                    if(j>n||j<0){
                        break;
                    }
                    is_sieve[j]=1;
                    sieve[j]=i;
                }
            }
        }
    }
    static void calc(int n){
        int i,j;
        dp[n-1]=0;
        if(n>1)
        dp[n-2]=1;
        for(i=n-3;i>=0;i--){
            long ind=n-i-1;
            dp[i]=((ind*(long)mypow(10,ind-1))%MOD+dp[i+1])%MOD;
        }
    }
    static long mypow(long x,long y){
        long temp; 
        if( y == 0) 
            return 1; 
        temp = mypow(x, y/2); 
        if (y%2 == 0) 
            return (temp*temp)%MOD; 
        else
            return ((x*temp)%MOD*(temp)%MOD)%MOD; 
    }
    static long dist[],dp[];
    static int visited[][];
    static ArrayList<Integer> adj[];
    //static int dp[][][];
    static int R,G,B,MOD=1000000007;
    static int[] par,size;
    static int[] sieve,is_sieve;
    static TreeSet<Integer> tr;
    static char ch[][], ch1[][];
    
    public static void main(String args[]){
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter w = new PrintWriter(outputStream);
        int t,i,j,tno=0;
        //t=in.nextInt();
        t=1;
        while(t-->0){
            int n=in.nextInt();
            // w.println("n = "+n);
            // w.flush();
            if(n<=100){
                w.println("? 1");
                w.flush();
                i=2;
                int x=in.nextInt();
                while(x!=1){
                    w.println("? "+i);
                    w.flush();
                    x=in.nextInt();
                    i++;
                }
                w.println("! "+(i-1));
                w.flush();
            }else{
                int li=1,ri=n;
                w.println("? "+li);
                w.flush();
                int l=in.nextInt();
                w.println("? "+ri);
                w.flush();
                int count=0;
                int r=in.nextInt();
                while(true){
                    count+=3;
                    int midi=(li+ri)/2;
                    w.println("? "+midi);
                    w.flush();
                    int mid,midl,midr;
                    mid=in.nextInt();
                    if(midi==1||midi==n){
                        w.println("! "+Math.max(midi,1));
                        w.flush();
                        break;
                    }
                    w.println("? "+(midi-1));
                    w.flush();
                    midl=in.nextInt();
                    if(mid==1){
                        w.println("! "+Math.max(midi,1));
                        w.flush();
                        break;
                    }
                    w.println("? "+(midi+1));
                    w.flush();
                    midr=in.nextInt();
                    if(midl==1){
                        w.println("! "+Math.max(midi-1,1));
                        w.flush();
                        break;
                    }
                    if(midr==1){
                        w.println("! "+Math.max(midi+1,1));
                        w.flush();
                        break;
                    }
                    if((mid<=midl&&mid<=midr)){
                        w.println("! "+Math.max(midi,1));
                        w.flush();
                        break;
                    }else if(mid>midl&&mid<midr){
                        ri=midi;
                    }else{
                        li=midi;
                    }
                }
            }
            
        }
        w.close();
    }
}