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

public class cf719 {

   
      public static int query(int l,int r) throws Exception{
          if(l>=r)return -1;

          InputStreamReader ip=new InputStreamReader(System.in);
          BufferedReader br = new BufferedReader(ip);
          
          System.out.println("? "+(l+1)+" "+(r+1));
          int ans=Integer.parseInt(br.readLine());

          return ans-1;
      }
      //For HardVersion the resulting number of queries is 2+⌈𝑙𝑜𝑔(base2)10^5⌉=19.
      //For EasyVersion the resulting number of queries is 2⋅⌈𝑙𝑜𝑔2105⌉=34.
      public static void HardVersion() throws Exception{
        InputStreamReader ip=new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ip);
        int n =Integer.parseInt(br.readLine());
        // String[] strs=(br.readLine()).trim().split(" ");
        
        int l=0,r=n;   //so that segment divide equally by mid  [l,mid) [mid,r)

        int smax=query(l, r-1);  //segment max
        int ans=0;

        if(smax==0 || query(0, smax)!=smax){
            l=smax;  r=n-1;   //Max lie in right segment 

            while((r-l)>1){
                int mid=l+(r-l)/2;
                if(query(smax,mid)==smax){
                    r=mid;
                }else{
                    l=mid;
                }
            }
           
         System.out.println("! "+(r+1));     //+r+" "
        }else{
            l=0;  r=smax;   //Max lie in left segment 

            while((r-l)>1){
                int mid=l+(r-l)/2;
                if(query(mid,smax)==smax){
                    l=mid;
                }else{
                    r=mid;
                }
            }
           
         System.out.println("! "+(l+1));  
        }

    }

      public static void EasyVersion() throws Exception{
        InputStreamReader ip=new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ip);
        int n =Integer.parseInt(br.readLine());
        // String[] strs=(br.readLine()).trim().split(" ");
        
        int l=0,r=n;   //so that segment divide equally by mid  [l,mid) [mid,r)

        int ans=0;
        while((r-l)>1){  //  query possible for segment of size >1
            int mid=l+(r-l)/2;
            int smax=query(l, r-1);  //segment max
            
            if(smax<mid){
                if(query(l, mid-1)==smax){
                    r=mid;
                }else{ l=mid; }
            }else{
                if(query(mid, r-1)==smax){
                    l=mid;
                }else{
                    r=mid;
                }
            }
            // System.out.println(l+"  "+r);
        }

        System.out.println("! "+r);     //+r+" "
    }
	
   
//******************************************************************************************************************** */
    public static void main(String[] args) throws Exception{
        HardVersion();
     }

     public static void solve3() throws Exception{
        InputStreamReader ip=new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ip);
        int t = Integer.parseInt(br.readLine());
        StringBuilder asb=new StringBuilder();
		
       while(t-->0){
        int n =Integer.parseInt(br.readLine());
        String[] strs=(br.readLine()).trim().split(" ");
        // int n=Integer.parseInt(strs[0]),k=Integer.parseInt(strs[1]),r=Integer.parseInt(strs[2]),s=Integer.parseInt(strs[3]);
        //  String str=(br.readLine()).trim();
        
        //Rearrange Given Expression-   a𝑗−a𝑖=𝑗−𝑖    =>  aj-j == ai-i
        int[] arr=new int[n];
        HashMap<Integer,Integer> hm=new HashMap<>();

        for(int i=0;i<n;i++){ arr[i]=Integer.parseInt(strs[i]);
        hm.put((arr[i]-i), hm.getOrDefault((arr[i]-i), 0)+1); }

        
        long ans=0;
        for(int key:hm.keySet()){
            long ct=hm.get(key);
            ans+=(ct*(ct-1))/2;
        }
        
        // System.out.println(ans+" ct "+ct);
        System.out.println(ans);
       }
    }
	
   
 //******************************************************************************************************************** */
  
    public static long modInverse1(long a, long m){
        // int g = gcd(a, m);
        // if(g!=1) {System.out.println("Inverse Doesnot Exist");}  
        return binexp(a, m - 2, m);
       }
   
    public  static long binexp(long a, long b, long m){
        if (b == 0)return 1; 
            
        long res = binexp(a, b / 2, m);
        if (b % 2 == 1) return (( (res*res)%m )*a) % m;
        else return (res*res)%m;
    }

    //binexp
    public static long binexp(long a,long b){
        if(b==0)return 1;

        long res=binexp(a, b/2);

        if(b%2==1){
            return (((res*res))*a);
        }else return (res*res);
    }

    //Comparator Interface
    public static class comp implements Comparator<int[]>{
        public int compare(int[] a,int[] b){
            return a[0]-b[0];
        }
    }

	//gcd using Euclid's Division Algorithm  
    public static long gcd(long a,long b){   
        if(b==0)return a;
        else return gcd(b, a%b);
    }

	//check prime in root(n)
    public static int isprime(int n){
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0)return i;
        }

        return -1;   //means n is prime
    }

	//SOE
	static  int[] sieve;
	public static void SOE(int n){
        sieve=new int[n+1];

        // System.out.println("All prime number from 1 to n:-");
        
        for(int x=2;x<=n;x++){
            if(sieve[x]!=0){  //Not prime number
                continue;
            }
            // System.out.print(x+"  ");
            for(int u=2*x;u<=n;u+=x){
                sieve[u]=x;
            }
        }

		//If  sieve[i]=0 means 'i' is primr else 'i' is not prime 
    }

    //sort
     public static void sort(long[] arr) {
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int idx = (int) Math.random() * n;
			long temp = arr[i];  arr[i] = arr[idx];  arr[idx] = temp;  //swap
		}
		Arrays.sort(arr);
	}
 
	public static void sort(int[] arr) {
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int idx = (int) Math.random() * n;
			int temp = arr[i];  arr[i] = arr[idx]; arr[idx] = temp;  //swap
		}
		Arrays.sort(arr);
	}
    //1d print
    public static void print(int[] dp) {
		for (int val : dp) {
			System.out.print(val + " ");
		}
		System.out.println();
	}
 
	public static void print(long[] dp) {//Method Overloading
		for (long val : dp) {
			System.out.print(val + " ");
		}
		System.out.println();
	}  
    //2d print
	public static void print(long[][] dp) {//Method Overloading
		for (long[] a : dp) {
			for (long val : a) {
				System.out.print(val + " ");
			}
			System.out.println();
		}
	}
 
	public static void print(int[][] dp) {
		for (int[] a : dp) {
			for (int val : a) {
				System.out.print(val + " ");
			}
			System.out.println();
		}
	}
 
	
}