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.StringTokenizer;

public class GuessingTheGreatestHard {
    MyScanner scanner = new MyScanner();

    private int solve(int n) {
        if (n == 2) {
            int secMax = ask(0, 1);
            if (secMax == 0) return 1;
            else return 0;
        }

        int start = 0, end = n - 1;
        int secMax = ask(start, end);
        boolean maxIsRight = secMax == 0 || secMax != end && ask(secMax, end) == secMax;
        if (maxIsRight) {// Guess Right
            while (start <= end) {
                int mid = start + (end - start) / 2;
//                if (mid == 0) break;
                int val = ask(0, mid); // Right
                if (val == secMax) {
                    end = mid - 1;
                }
                else {
                    start = mid + 1;
                }
            }
            return start;
        }
        else {
            start = 0;
            end = n - 1;
            while (start <= end) {
                int mid = start + (end - start) / 2;
//                if (mid == n - 1) break;
                int val = ask(mid, n - 1);
                if (val == secMax) {
                    start = mid + 1;
                }
                else {
                    end = mid - 1;
                }
            }
            return end;
        }
    }

//    private int ask(int l, int r) {
////        int[] arr = {23, 81, 16, 91, 13, 98, 64, 12, 19, 99, 8, 33, 35, 27, 29, 51, 68, 58, 86, 93, 50, 96, 17, 22, 4, 78, 76, 44, 74, 89, 24, 90, 38, 80, 85, 59, 70, 53, 49, 87, 65, 83, 69, 10, 56, 32, 11, 88, 31, 100, 79, 46, 48, 75, 7, 72, 36, 97, 21, 62, 95, 1, 92, 18, 52, 54, 66, 2, 47, 84, 15, 42, 73, 39, 26, 5, 77, 14, 6, 30, 71, 9, 55, 57, 41, 40, 60, 20, 25, 43, 45, 28, 34, 37, 3, 67, 82, 94, 61, 63};
////        int[] arr = {5,1,4,2,3};
//        int[] arr = {1, 2};
//        int first = -1, second = -1;
//        for (int i = l; i <= r; i++) {
//            if (first == -1 || arr[i] > arr[first]) {
//                second = first;
//                first = i;
//            }
//            else if (second == -1 || arr[i] > arr[second]) {
//                second = i;
//            }
//        }
//        return second;
//    }
    private int ask(int l, int r) {
        System.out.println("? " + (l + 1) + " " + (r + 1));
        System.out.flush();
        int ans = scanner.nextInt();
        return ans - 1;
    }

    private void print(int n) {
        System.out.println("! " + (n + 1));
        System.out.flush();
    }

    public static void main(String[] args) {
        GuessingTheGreatestHard test = new GuessingTheGreatestHard();
//        int t = test.scanner.nextInt();
//        for (int i = 0; i < t; i++) {
        int n = test.scanner.nextInt();
        int ans = test.solve(n);
        test.print(ans);
//        }
    }

    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());
        }

        int[] nextIntArray(int len) {
            int[] arr = new int[len];
            for (int i = 0; i < len; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        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;
        }
    }
}