Problem: The only difference between the easy and the hard version is the limit to the number of queries.

This is an interactive problem.

There is an array a of n different numbers. In one query you can ask the position of the second maximum element in a subsegment a[l..r]. Find the position of the maximum element in the array in no more than 20 queries.

A subsegment a[l..r] is all the elements a_l, a_{l + 1}, ..., a_r. After asking this subsegment you will be given the position of the second maximum from this subsegment in the whole array.

Input

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of elements in the array.

Interaction

You can ask queries by printing "? l r" (1 ≤ l < r ≤ n). The answer is the index of the second maximum of all elements a_l, a_{l + 1}, ..., a_r. Array a is fixed beforehand and can't be changed in time of interaction.

You can output the answer by printing "! p", where p is the index of the maximum element in the array.

You can ask no more than 20 queries. Printing the answer doesn't count as a query.

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 



Hacks

To make a hack, use the following test format.

In the first line output a single integer n (2 ≤ n ≤ 10^5). In the second line output a permutation of n integers 1 to n. The position of n in the permutation is the position of the maximum

Example

Input


5

3

4



Output


? 1 5

? 4 5

! 1

Note

In the sample suppose a is [5, 1, 4, 2, 3]. So after asking the [1..5] subsegment 4 is second to max value, and it's position is 3. After asking the [4..5] subsegment 2 is second to max value and it's position in the whole array is 4.

Note that there are other arrays a that would produce the same interaction, and the answer for them might be different. Example output is given in purpose of understanding the interaction.

Solution (in JAVA):

Solution:



import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;

public class Main {
    static class point {
        long val, time, t3;

        point(long val, long time, int t3) {
            this.val = val;
            this.time = time;

            this.t3 = t3;
        }
    }
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;

        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }


    static class comp implements Comparator<point> {
        public int compare(point a, point b) {
            if (a.val == b.val) {
                return Long.compare(b.time, a.time);
            }
            return Long.compare(a.val, b.val);
        }
    }

    static class TreeNode {
        int val;
        TreeNode left,right;
        TreeNode(int val){
            this.val=val;left=null;right=null;
        }
    }
    static TreeNode maxx(int start,int end,int[] arr){
        if(start>end){
            return null;
        }
        int ind=0;
        int max=-1;
        for(int j=start;j<=end;j++){
            if(arr[j]>max){
                max=arr[j];
                ind=j;
            }
        }
        TreeNode jj=new TreeNode(arr[ind]);
        jj.left=maxx(start,ind-1,arr);
        jj.right=maxx(ind+1,end,arr);
        return jj;

    }
    static void dfs(TreeNode root,int dep){
        if(root==null){
            return;
        }
        ans[hashMap.get(root.val)]=dep;
        dfs(root.left,dep+1);
        dfs(root.right,dep+1);
    }
    static int[] ans;
   static HashMap<Integer,Integer> hashMap;
   static class pont{
       int val,index;
       pont(int val,int index){
           this.val=val;
           this.index=index;
       }
   }
   static class compr implements Comparator<pont>{
       public int compare(pont a,pont b){
           return a.val-b.val;
       }
   }
    static class poin{
       int src;
       long val;
       poin(int src,long val){
           this.src=src;
           this.val=val;
       }
    }
    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        int n=s.nextInt();
        int low=1,high=n;
        System.out.println("? "+low+" "+high );
        System.out.println();
        System.out.flush();
        int secondmaxindex=s.nextInt();
        if(low==secondmaxindex){
            System.out.println("? "+secondmaxindex+" "+high );
            System.out.println();
            System.out.flush();
            int secondmax2=s.nextInt();
            if(secondmax2!=secondmaxindex){
                high=secondmaxindex-1;
                low=1;
                int ans=low;
                while(low<=high){
                    int mid=(low)+(high-low)/2;
                    if(mid==secondmaxindex){
                        break;
                    }

                    System.out.println("? "+mid+" "+secondmaxindex );
                    System.out.println();
                    System.out.flush();
                    int inpu=s.nextInt();
                    if(inpu==secondmaxindex){
                        ans=mid;
                        low=mid+1;
                    }else{
                        high=mid-1;
                    }
                }
                System.out.println("! "+" "+ans);
                System.out.flush();

            }else{
                low=secondmaxindex+1;
                high=n;
                int ans=high;
                while(low<=high){
                    int mid=(low)+(high-low)/2;
                    if(mid==secondmaxindex){
                        break;
                    }
                    System.out.println("? "+secondmaxindex+" "+mid);
                    System.out.println();
                    System.out.flush();
                    int inpu=s.nextInt();
                    if(inpu==secondmaxindex){
                        ans=mid;
                        high=mid-1;
                    }else{
                        low=mid+1;
                    }
                }
                System.out.println("! "+" "+ans);
                System.out.flush();
            }

        }

        else{
        System.out.println("? "+low+" "+secondmaxindex );
        System.out.println();
        System.out.flush();
            int secondmax2=s.nextInt();
            if(secondmax2==secondmaxindex){
                high=secondmaxindex-1;
                low=1;
                int ans=low;
                while(low<=high){
                    int mid=(low)+(high-low)/2;
                    if(mid==secondmaxindex){
                        break;
                    }

                    System.out.println("? "+mid+" "+secondmaxindex );
                    System.out.println();
                    System.out.flush();
                    int inpu=s.nextInt();
                    if(inpu==secondmaxindex){
                        ans=mid;
                        low=mid+1;
                    }else{
                        high=mid-1;
                    }
                }
                System.out.println("! "+" "+ans);
                System.out.flush();

            }else{
                low=secondmaxindex+1;
                high=n;
                int ans=high;
                while(low<=high){
                    int mid=(low)+(high-low)/2;
                    if(mid==secondmaxindex){
                        break;
                    }
                    System.out.println("? "+secondmaxindex+" "+mid);
                    System.out.println();
                    System.out.flush();
                    int inpu=s.nextInt();
                    if(inpu==secondmaxindex){
                        ans=mid;
                        high=mid-1;
                    }else{
                        low=mid+1;
                    }
                }
                System.out.println("! "+" "+ans);
                System.out.flush();
            }

        }


//        int t=s.nextInt();
//        int t=1;
//        for(int jj=0;jj<t;jj++){
//            int n=s.nextInt();
//            HashMap<Integer,HashMap<Integer,Integer>> has=new HashMap<>();
//            int m=s.nextInt();
//            int x=s.nextInt();
//            int y=s.nextInt();
//            long[] ti=new long[m];
//            long[] ki=new long[m];
//            HashMap<Integer,HashSet<Integer>> hash=new HashMap<>();
//            for(int i=0;i<=n;i++){
//                has.put(i,new HashMap<>());
//                hash.put(i,new HashSet<>());
//            }
//            for(int i=0;i<m;i++){
//                int a=s.nextInt();
//                int b=s.nextInt();
////                if(has.get(a)==null){
////                    has.put(a,new HashMap<>());
////                }
////                if(has.get(b)==null){
////                    has.put(b,new HashMap<>());
////                }
//                has.get(a).put(b,i);
//                has.get(b).put(a,i);
//                ti[i]=s.nextLong();
//                ki[i]=s.nextLong();
//            }
//
//            long[] vis=new long[n+1];
//            Arrays.fill(vis,Long.MAX_VALUE);
//            vis[x]=0;
//            Queue<poin> qu=new LinkedList<>();
//            qu.add(new poin(x,0));
//            long ans=Long.MAX_VALUE;
//            while(!qu.isEmpty()){
//                poin te=qu.poll();
//                if(te.src==y){
//                    ans=Math.min(ans,te.val);continue;
//                }
//                for(Integer v:has.get(te.src).keySet()){
//                    long ll=(ki[has.get(te.src).get(v)]+(te.val%ki[has.get(te.src).get(v)]))%ki[has.get(te.src).get(v)]+ti[has.get(te.src).get(v)];
////                    if(te.val>ki[has.get(te.src).get(v)]){
////                        long ij=(long)Math.ceil((double)te.val/(double)ki[has.get(te.src).get(v)]);
////                        ll=(long)((long)ij*(long)ki[has.get(te.src).get(v)]);
////                    }else{
////                       // long ij=(long)Math.ceil((double)ki[has.get(te.src).get(v)]/(double)te.val);
////                        if(te.val==0){
////                            ll=0;
////                        }else{
////                        ll=(long)((long)(long)ki[has.get(te.src).get(v)]);}
////                    }
////                    ll=(long)((long)ll+(long)ti[has.get(te.src).get(v)]);
////                    long ll= (long)Math.max((long)((long)te.val+(long)ti[has.get(te.src).get(v)]), (long)((long)ki[has.get(te.src).get(v)]*(long)Math.floor((double)ki[has.get(te.src).get(v)]/(double)(te.val+ti[has.get(te.src).get(v)]))));
////                    if( !hash.get(v).contains(te.src) ){
////                        vis[v]=ll;
////                        hash.get(v).add(te.src);
////                        qu.add(new poin( v,vis[v]));
////                    }
//                    if(vis[v]>=ll){
//                        vis[v]=ll;
////                        hash.get(v).add(te.src);
//                        qu.add(new poin( v,vis[v]));
//
//                    }
//                }
//            }
//            if(ans==Long.MAX_VALUE){
//                System.out.println(-1);
//            }else{
//            System.out.println(ans);}
//        }
    }
}