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.*;
import java.util.ArrayList;
import java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class cf {
    static final int SCAN_LINE_LENGTH = 100002;
    private static final boolean thread = false;
    @SuppressWarnings("all")
    static final boolean HAS_TEST_CASES = (1 == 0) ? true : false;

    static int n, a[], e[][], vis[], m, b[];
    @SuppressWarnings("all")
    private static Vector<Integer> adj[], v = new Vector<>();

    @SuppressWarnings("unchecked")
    static void solve() throws Exception {
        n = ni();
        int a = -1, l = 1, r = n, m;
        m = get(l, r);
        if (m != l && m == get(l, m)) {
            r = m - 1;
            a = r;
            while (l <= r) {
                int mid = (l + 1 + r) / 2;
                if (r - l == 1) {
                    a = (get(l, r) == l) ? r : l;
                    break;
                }
                if (get(mid, m) == m) {
                    a = mid;
                    l = mid + 1;
                } else
                    r = mid - 1;
            }
        } else {
            l = m + 1;
            a = l;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (r - l == 1) {
                    a = (get(l, r) == l) ? r : l;
                    break;
                }
                if (get(m, mid) == m) {
                    a = mid;
                    r = mid - 1;
                } else
                    l = mid + 1;
            }
        }
        pni("! " + a);
    }

    private static int get(int l, int r) throws IOException {
        int m;
        if (l >= r)
            return -1;
        pni("? " + l + " " + r);
        m = ni();
        return m;
    }

    public static void main(final String[] args) throws Exception {
        if (!thread) {
            final int testcases = HAS_TEST_CASES ? ni() : 1;
            for (int i = 1; i <= testcases; i++) {
                // pni(i + " t");
                // out.print("Case #" + (i + 1) + ": ");
                try {
                    solve();
                } catch (final Exception e) {
                    // pni("idk Exception");
                    // e.printStackTrace(System.err);
                    // System.exit(0);
                    pni(i);
                    throw e;
                }
            }
            out.flush();
        }
        r.close();
        out.close();
    }

    @SuppressWarnings("all")
    private static final int MOD = (int) (1e9 + 7), MOD_FFT = 998244353;
    private static final Reader r = new Reader();
    private static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static long[] enumPows(int a, int n, int mod) {
        a %= mod;
        long[] pows = new long[n + 1];
        pows[0] = 1;
        for (int i = 1; i <= n; i++)
            pows[i] = pows[i - 1] * a % mod;
        return pows;
    }

    @SuppressWarnings("all")
    private static boolean eq(long a, long b) {
        return Long.compare(a, b) == 0;
    }

    @SuppressWarnings("all")
    private static ArrayList<Integer> seive(int n) {
        ArrayList<Integer> p = new ArrayList<>();
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (f[i] == 1)
                continue;
            for (int j = i * i; j <= n && j < f.length; j += i) {
                f[j] = 1;
            }
        }
        for (int i = 2; i < f.length; i++) {
            if (f[i] == 0)
                p.add(i);
        }
        return p;
    }

    @SuppressWarnings("all")
    private static void s(int[] a) {
        Integer[] t = new Integer[a.length];
        for (int i = 0; i < t.length; i++) {
            t[i] = a[i];
        }
        sort(t);
        for (int i = 0; i < t.length; i++) {
            a[i] = t[i];
        }
    }

    int pow(int a, int b, int m) {
        int ans = 1;
        while (b != 0) {
            if ((b & 1) != 0)
                ans = (ans * a) % m;
            b /= 2;
            a = (a * a) % m;
        }
        return ans;
    }

    int modinv(int k) {
        return pow(k, MOD - 2, MOD);
    }

    @SuppressWarnings("all")
    private static void swap(final int i, final int j) {
        final int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    @SuppressWarnings("all")
    private static boolean isMulOverflow(final long A, final long B) {
        if (A == 0 || B == 0)
            return false;
        final long result = A * B;
        if (A == result / B)
            return true;
        return false;
    }

    @SuppressWarnings("all")
    private static int gcd(final int a, final int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    @SuppressWarnings("all")
    private static long gcd(final long a, final long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    @SuppressWarnings("all")
    private static class Pair<T, E> implements Comparable<Pair<T, E>> {
        T fir;
        E snd;

        Pair() {
        }

        Pair(final T x, final E y) {
            this.fir = x;
            this.snd = y;
        }

        // @Override
        // @SuppressWarnings("unchecked")
        // public int compareTo(final Pair<T, E> o) {
        // final int c = ((Comparable<T>) fir).compareTo(o.fir);
        // return c != 0 ? c : ((Comparable<E>) snd).compareTo(o.snd);
        // }
        @Override
        @SuppressWarnings("unchecked")
        public int compareTo(final Pair<T, E> o) {
            final int c = ((Comparable<T>) fir).compareTo(o.fir);
            return c;
        }

    }

    @SuppressWarnings("all")
    private static class pi implements Comparable<pi> {
        int fir, snd;

        pi() {
        }

        pi(final int a, final int b) {
            fir = a;
            snd = b;
        }

        public int compareTo(final pi o) {
            return fir == o.fir ? snd - o.snd : fir - o.fir;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + fir;
            result = prime * result + snd;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            pi other = (pi) obj;
            if (fir != other.fir)
                return false;
            if (snd != other.snd)
                return false;
            return true;
        }

    }

    @SuppressWarnings("all")
    private static <T> void checkV(final Vector<T> adj[], final int i) {
        adj[i] = adj[i] == null ? new Vector<>() : adj[i];
    }

    @SuppressWarnings("all")
    private static int[] na(final int n) throws Exception {
        final int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = ni();
        }
        return a;
    }

    @SuppressWarnings("all")
    private static int[] na1(final int n) throws Exception {
        final int[] a = new int[n + 1];
        for (int i = 1; i < a.length; i++) {
            a[i] = ni();
        }
        return a;
    }

    @SuppressWarnings("all")
    private static String n() throws IOException {
        return r.readToken();
    }

    @SuppressWarnings("all")
    private static char[] ns() throws IOException {
        return r.readToken().toCharArray();
    }

    @SuppressWarnings("all")
    private static String nln() throws IOException {
        return r.readLine();
    }

    private static int ni() throws IOException {
        return r.nextInt();
    }

    @SuppressWarnings("all")
    private static long nl() throws IOException {
        return r.nextLong();
    }

    @SuppressWarnings("all")
    private static double nd() throws IOException {
        return r.nextDouble();
    }

    @SuppressWarnings("all")
    private static void p(final Object o) {
        out.print(o);
    }

    @SuppressWarnings("all")
    private static void pn(final Object o) {
        out.println(o);
    }

    @SuppressWarnings("all")
    private static void pn() {
        out.println("");
    }

    @SuppressWarnings("all")
    private static void pi(final Object o) {
        out.print(o);
        out.flush();
    }

    @SuppressWarnings("all")
    private static void pni() {
        out.println("");
        out.flush();
    }

    private static void pni(final Object o) {
        out.println(o);
        out.flush();
    }

    private static class Reader {
        private final int BUFFER_SIZE = 1 << 17;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        // private StringTokenizer st;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        @SuppressWarnings("all")
        public Reader(final String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        final byte[] buf = new byte[SCAN_LINE_LENGTH];

        public String readLine() throws IOException {
            int cnt = 0;
            int c;
            o: while ((c = read()) != -1) {
                if (c == '\n')
                    if (cnt == 0)
                        continue o;
                    else
                        break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public String readToken() throws IOException {
            int cnt = 0;
            int c;
            o: while ((c = read()) != -1) {
                if (!(c >= 33 && c <= 126))
                    if (cnt == 0)
                        continue o;
                    else
                        break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

    // static {
    // if (thread)
    // new Thread(null, new Runnable() {
    // @Override
    // public void run() {
    // try {
    // final int testcases = HAS_TEST_CASES ? ni() : 1;
    // for (int i = 1; i <= testcases; i++) {
    // // out.print("Case #" + (i + 1) + ": ");
    // try {
    // solve();
    // } catch (final ArrayIndexOutOfBoundsException e) {
    // e.printStackTrace(System.err);
    // System.exit(-1);
    // } catch (final Exception e) {
    // pni("idk Exception in solve");
    // e.printStackTrace(System.err);
    // System.exit(-1);
    // }
    // }
    // out.flush();
    // } catch (final Throwable t) {
    // t.printStackTrace(System.err);
    // System.exit(-1);
    // }
    // }
    // }, "rec", (1L << 28)).start();
    // }

    @SuppressWarnings({ "all", })
    private static <T> T deepCopy(final T old) {
        try {
            return (T) deepCopyObject(old);
        } catch (final IOException | ClassNotFoundException e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
        return null;
    }

    private static Object deepCopyObject(final Object oldObj) throws IOException, ClassNotFoundException {
        ObjectOutputStream oos = null;
        ObjectInputStream ois = null;
        try {
            final ByteArrayOutputStream bos = new ByteArrayOutputStream(); // A
            oos = new ObjectOutputStream(bos); // B
            // serialize and pass the object
            oos.writeObject(oldObj); // C
            oos.flush(); // D
            final ByteArrayInputStream bin = new ByteArrayInputStream(bos.toByteArray()); // E
            ois = new ObjectInputStream(bin); // F
            // return the new object
            return ois.readObject(); // G
        } catch (final ClassNotFoundException e) {
            pni("Exception in ObjectCloner = " + e);
            throw (e);
        } finally {
            oos.close();
            ois.close();
        }
    }

}