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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static class DisjointUnionSets {
        int[] rank, parent;
        int n;

        // Constructor
        public DisjointUnionSets(int n)
        {
            rank = new int[n];
            parent = new int[n];
            this.n = n;
            makeSet();
        }

        // Creates n sets with single item in each
        void makeSet()
        {
            for (int i = 0; i < n; i++) {
                // Initially, all elements are in
                // their own set.
                parent[i] = i;
            }
        }

        // Returns representative of x's set
        int find(int x)
        {
            // Finds the representative of the set
            // that x is an element of
            if (parent[x] != x) {
                // if x is not the parent of itself
                // Then x is not the representative of
                // his set,
                parent[x] = find(parent[x]);

                // so we recursively call Find on its parent
                // and move i's node directly under the
                // representative of this set
            }

            return parent[x];
        }

        // Unites the set that includes x and the set
        // that includes x
        void union(int x, int y)
        {
            // Find representatives of two sets
            int xRoot = find(x), yRoot = find(y);

            // Elements are in the same set, no need
            // to unite anything.
            if (xRoot == yRoot)
                return;

            // If x's rank is less than y's rank
            if (rank[xRoot] < rank[yRoot])

                // Then move x under y  so that depth
                // of tree remains less
                parent[xRoot] = yRoot;

                // Else if y's rank is less than x's rank
            else if (rank[yRoot] < rank[xRoot])

                // Then move y under x so that depth of
                // tree remains less
                parent[yRoot] = xRoot;

            else // if ranks are the same
            {
                // Then move y under x (doesn't matter
                // which one goes where)
                parent[yRoot] = xRoot;

                // And increment the result tree's
                // rank by 1
                rank[xRoot] = rank[xRoot] + 1;
            }
        }
    }
    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    static class HashMultiSet<T> implements Iterable<T>
    { private final HashMap<T,Integer> map;
        private int size;
        public HashMultiSet(){map=new HashMap<>(); size=0;}
        public void clear(){map.clear(); size=0;}
        public int size(){return size;}
        public int setSize(){return map.size();}
        public boolean contains(T a){return map.containsKey(a);}
        public boolean isEmpty(){return size==0;}
        public Integer get(T a){return map.getOrDefault(a,0);}
        public void add(T a, int count)
        {
            int cur=get(a);map.put(a,cur+count); size+=count;
            if(cur+count==0) map.remove(a);
        }
        public void addOne(T a){add(a,1);}
        public void remove(T a, int count){add(a,Math.max(-get(a),-count));}
        public void removeOne(T a){remove(a,1);}
        public void removeAll(T a){remove(a,Integer.MAX_VALUE-10);}

        public Iterator<T> iterator()
        {
            return new Iterator<>()
            {
                private final Iterator<T> iter = map.keySet().iterator();
                private int count = 0; private T curElement;

                public boolean hasNext(){return iter.hasNext()||count>0;}
                public T next()
                {
                    if(count==0)
                    {
                        curElement=iter.next();
                        count=get(curElement);
                    }
                    count--; return curElement;
                }
            };
        }
    }
    private  static long abs(long x){ if(x < 0) x*=-1l;return x; }
    private  static int abs(int x){ if(x < 0) x*=-1;return x; }

//    public static int get(HashMap<Integer, Deque<Integer> > a, int key ){
//        return a.get(key).getLast();
//    }
//    public  static  void removeLast (HashMap<Integer,Deque<Integer> > a, int key){
//        if(a.containsKey(key)){
//            a.get(key).removeLast();
//            if(a.get(key).size() == 0) a.remove(key);
//        }
//    }
//    public  static  void add(HashMap<Integer,Deque<Integer>> a, int key, int val){
//        if(a.containsKey(key)){
//            a.get(key).addLast(val);
//        }else{
//            Deque<Integer> b = new LinkedList<>();
//            b.addLast(val);
//            a.put(key,b);
//        }
//    }

    private static int askRange(int l ,int r){
        if(l == r) return l;
        MyScanner sc = new MyScanner();
        System.out.println("? "+l+" "+r);
        System.out.flush();
        return  sc.nextInt();
    }

    private static int binr(int l ,int r,int v){
        if(l > r) return Integer.MAX_VALUE;
       int mid = (r+l) /2;
       if(askRange(v,mid) == v){
           int x = binr(l,mid-1,v);
           return Math.min(x,mid);
       }else{
           int x = binr(mid+1,r,v);
           return x;
       }

    }
    private  static int binl(int l,int r,int v){
        if (l > r) return Integer.MIN_VALUE;
        int mid = (l+r) /2;
        if(askRange(mid,v) == v){
            int x = binl(mid+1,r,v);
            return Math.max(x,mid);
        }else{
            int x = binl(l,mid-1,v);
            return x;
        }
    }
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        int n = sc.nextInt();
        int v = askRange(1,n);
        int v1 = askRange(v,n);
        if(v == v1 && v != n){
            System.out.println("! " +binr(v+1,n,v));
        }else{
            System.out.println("! "+binl(1,v-1,v));
        }
    }
}