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.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.io.*;

public class Equal {


    static class pair implements Comparable<pair> {
        int x;
        int y;

        public pair(int u, int  v) {
            this.x = u;
            this.y = v;
        }

        @Override
        public int compareTo(pair o) {
            return o.x-x;
        }
    }
    static int[][]mem=new int[1001][1001];
//    static int dp(int n,int k){
//        if(n>=mem.length)
//            return 0;
//        if(k<0||k>=mem.length)
//            return 0;
//        if(mem[n][k]!=-1)
//            return mem[n][k];
//    }
    static String timeInc(String time,int h,int m){
        String []s =time.split(":");
        int i=0;
        int hh=0;
        int mm=0;
        while (i<s[0].length()&&s[0].charAt(i)=='0'){
            i++;
        }
        if(i<s[0].length())
            hh=Integer.parseInt(s[0].substring(i));
        i=0;
        while (i<s[1].length()&&s[1].charAt(i)=='0'){
            i++;
        }
        if(i<s[1].length())
            mm=Integer.parseInt(s[1].substring(i));
        mm++;
        if(mm%m==0){
            mm=0;
            hh++;
            if(hh%h==0)
                hh=0;
        }
        String hs=""+hh;
        while(hs.length()<2)
            hs="0"+hs;
        String ms=""+mm;
        while (ms.length()<2)
            ms="0"+ms;
        return hs+":"+ms;

    }

    static boolean validMirror(String s,int h,int m){
        HashSet<Character>hs=new HashSet<>();
        hs.add('3');
        hs.add('4');
        hs.add('6');
        hs.add('7');
        hs.add('9');
        for (int i = 0; i <s.length() ; i++) {
            if(hs.contains(s.charAt(i))){
                return false;
            }
        }
        String mirrored="";
        for (int i = s.length()-1; i >=0 ; i--) {
            if(s.charAt(i)=='5'){
                mirrored+="2";
                continue;
            }
            if(s.charAt(i)=='2'){
                mirrored+="5";
                continue;
            }
            mirrored+=s.charAt(i);

        }
        int i=0;
        int hh=0;
        int mm=0;
        String []s2 =mirrored.split(":");
        while (i<s2[0].length()&&s2[0].charAt(i)=='0'){
            i++;
        }
        if(i<s2[0].length())
            hh=Integer.parseInt(s2[0].substring(i));
        i=0;
        while (i<s2[1].length()&&s2[1].charAt(i)=='0'){
            i++;
        }
        if(i<s2[1].length())
            mm=Integer.parseInt(s2[1].substring(i));
        if(hh>=h||mm>=m)
            return false;

        return true;
    }


    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new FileReader("name.in"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PrintWriter out = new PrintWriter(System.out);
        int n=Integer.parseInt(br.readLine());
        boolean found=false;
        int p=-1;
        int q=0;

        System.out.println("? 1 "+n);
        int second=Integer.parseInt(br.readLine());
        int beg=-1;
        int end=-1;
        if(second>1&&second!=n) {
            System.out.println("? 1 " + second);

            int before = Integer.parseInt(br.readLine());

            if (before == second) {

                beg = 1;
                end = second;
            } else {

                beg = second;
                end = n;


            }
        }
        else{
            beg=1;
            end=n;
        }

        while(!found&&q<20){

            int mid=(beg+end)>>1;

            if(end-beg==1){
                if(end<=second)
                  mid=end;
                else
                    mid=beg;
                if(end==second||beg==second){
                    found=true;
                    p=end+beg-second;
                    break;
                }
            }
            if(mid>second){
                System.out.println("? "+second+" "+mid);
            }
            else {
                System.out.println("? "+mid+" "+second);
            }
            int x=Integer.parseInt(br.readLine());
            if(end-beg==1){
                found=true;
                if(x==second)
                    p=mid;
                else {
                    if(end<=second)
                        p=beg;
                    else p=end;
                }
            }
            else {
                if (x == second) {
                    if (mid < second) {
                        if(second-mid==1){
                            found=true;
                            p=mid;
                        }
                        beg = mid;
                    } else {
                        end = mid;
                        if(mid-second==1){
                            found=true;
                            p=mid;
                        }
                    }
                } else {
                    if (mid < second) {
                        if(mid-beg==1){
                            found=true;
                            p=beg;
                        }
                        end = mid;
                    } else {
                        if(end-mid==1){
                            found=true;
                            p=end;
                        }
                        beg = mid;
                    }
                }
            }
            q++;

        }
        System.out.println("! "+p);
        out.flush();
        out.close();

    }

}