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

public final class Solution {


    static PrintWriter out = new PrintWriter(System.out);
    static FastReader in = new FastReader();
    static long mod = (long) 1e9 + 7;
    static Pair[] moves = new Pair[]{new Pair(-1, 0), new Pair(1, 0), new Pair(0, -1), new Pair(0, 1)};

    public static void main(String[] args) {
        int t = 1;

        out:
        while (t-- > 0) {
            int n = i();

            int i1 = ask(0, n - 1);
            int i2 = i1 > 0 ? ask(0, i1) : -1;
            if (i1 == i2) {
                int l = 0;
                int r = i1 - 1;

                while (l < r) {
                    int m = (l + r + 1) / 2;
                    if (ask(m, i1) == i1) {
                        l = m;
                    } else {
                        r = m - 1;
                    }
                }
                out.println("! " + (l + 1));
                out.flush();
            } else {
                int l = i1 + 1;
                int r = n - 1;
                while (l < r) {
                    int m = (l + r) / 2;
                    if (ask(i1, m) == i1) {
                        r = m;
                    } else {
                        l = m + 1;
                    }
                }
                out.println("! " + (l + 1));
                out.flush();
            }
        }
        out.flush();
    }

    static int ask(int l, int r) {
        out.println("? " + (l + 1) + " " + (r + 1));
        out.flush();
        return i() - 1;
    }


    static boolean isPS(double number) {
        double sqrt = Math.sqrt(number);
        return ((sqrt - Math.floor(sqrt)) == 0);
    }

    static int sd(long i) {
        int d = 0;
        while (i > 0) {
            d += i % 10;
            i = i / 10;
        }
        return d;
    }

    static int[] leastPrime;

    static void sieveLinear(int N) {
        int[] primes = new int[N];
        int idx = 0;
        leastPrime = new int[N + 1];
        for (int i = 2; i <= N; i++) {
            if (leastPrime[i] == 0) {
                primes[idx++] = i;
                leastPrime[i] = i;
            }
            int curLP = leastPrime[i];
            for (int j = 0; j < idx; j++) {
                int p = primes[j];
                if (p > curLP || (long) p * i > N) {
                    break;
                } else {
                    leastPrime[p * i] = p;
                }
            }
        }
    }


    static int lower(long A[], long x) {
        int l = -1, r = A.length;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (A[m] >= x) {
                r = m;
            } else {
                l = m;
            }
        }
        return r;
    }

    static int upper(long A[], long x) {
        int l = -1, r = A.length;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (A[m] <= x) {
                l = m;
            } else {
                r = m;
            }
        }
        return l;
    }

    static void swap(int A[], int a, int b) {
        int t = A[a];
        A[a] = A[b];
        A[b] = t;
    }

    static int lowerBound(int A[], int low, int high, int x) {
        if (low > high) {
            if (x >= A[high]) {
                return A[high];
            }
        }

        int mid = (low + high) / 2;

        if (A[mid] == x) {
            return A[mid];
        }

        if (mid > 0 && A[mid - 1] <= x && x < A[mid]) {
            return A[mid - 1];
        }

        if (x < A[mid]) {
            return lowerBound(A, low, mid - 1, x);
        }

        return lowerBound(A, mid + 1, high, x);
    }


    static long pow(long a, long b) {
        long pow = 1;
        long x = a;
        while (b != 0) {
            if ((b & 1) != 0) {
                pow = (pow * x) % mod;
            }
            x = (x * x) % mod;
            b /= 2;
        }
        return pow;
    }

    static boolean isPrime(long N) {
        if (N <= 1) {
            return false;
        }
        if (N <= 3) {
            return true;
        }
        if (N % 2 == 0 || N % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= N; i = i + 6) {
            if (N % i == 0 || N % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    static void print(char A[]) {
        for (char c : A) {
            out.print(c);
        }
        out.println();
    }

    static void print(boolean A[]) {
        for (boolean c : A) {
            out.print(c + " ");
        }
        out.println();
    }

    static void print(int A[]) {
        for (int c : A) {
            out.print(c + " ");
        }
        out.println();
    }

    static void print(long A[]) {
        for (long i : A) {
            out.print(i + " ");
        }
        out.println();

    }

    static void print(List<Integer> A) {
        for (int a : A) {
            out.print(a + " ");
        }
    }

    static void printYes() {
        out.println("YES");
    }

    static void printNo() {
        out.println("NO");
    }

    static int i() {
        return in.nextInt();
    }

    static long l() {
        return in.nextLong();
    }

    static String s() {
        return in.nextLine();
    }

    static int[] input(int N) {
        int A[] = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        return A;
    }

    static long[] inputLong(int N) {
        long A[] = new long[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = in.nextLong();
        }
        return A;
    }

    static int GCD(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }

    static long GCD(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }

}

class BIT {

    int n;
    int[] tree;

    public BIT(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    public static int lowbit(int x) {
        return x & (-x);
    }

    public void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }

    public int query(int x) {
        int ans = 0;
        while (x > 0) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }

    public int query(int x, int y) {
        return query(y) - query(x - 1);
    }
}

class SegmentTree {

    long[] t;

    public SegmentTree(int n) {
        t = new long[n + n];
        Arrays.fill(t, Long.MIN_VALUE);
    }

    public long get(int i) {
        return t[i + t.length / 2];
    }

    public void add(int i, long value) {
        i += t.length / 2;
        t[i] = value;
        for (; i > 1; i >>= 1) {
            t[i >> 1] = Math.max(t[i], t[i ^ 1]);
        }
    }

    // max[a, b]
    public long max(int a, int b) {
        long res = Long.MIN_VALUE;
        for (a += t.length / 2, b += t.length / 2; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
            if ((a & 1) != 0) {
                res = Math.max(res, t[a]);
            }
            if ((b & 1) == 0) {
                res = Math.max(res, t[b]);
            }
        }
        return res;
    }
}

class Pair {

    int i, j;

    Pair(int i, int j) {
        this.i = i;
        this.j = j;
    }

}

class FastReader {

    BufferedReader br;
    StringTokenizer st;

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