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.*;
public class C {
  private static PrintWriter out;
  private static FS sc;
  private static class FS {
    StringTokenizer st;
    BufferedReader br;
    public FS() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }
    public String next() {
      while (st == null || !st.hasMoreElements()) {
        try {st = new StringTokenizer(br.readLine());}
        catch (IOException e) {e.printStackTrace();}
      }
      return st.nextToken();
    }
    public String nextLine() {
      String s = null;
      try {s = br.readLine();}
      catch (IOException e) {e.printStackTrace();}
      return s;
    }
    public int nextInt() {return Integer.parseInt(next());}
    public long nextLong() {return Long.parseLong(next());}
    public double nextDouble() {return Double.parseDouble(next());}
  }
  private static void bs(int l, int r, boolean left) {
    // out.println(left);
    int smax = 0, ans = -1;
    if (left) smax = l - 1;
    else smax = r + 1;
    while (l <= r) {
      int m = l + ((r-l)>>1);
      if (left) {
        out.println("? " + smax + " " + m);
        if (sc.nextInt() == smax) {ans = m; r = m-1;}
        else l = m+1;
      }
      else {
        out.println("? " + m + " " + smax);
        if (sc.nextInt() == smax) {ans = m; l = m + 1;}
        else r = m - 1;
      }
    }
    out.println("! " + ans);
  }
  public static void main(String[] args) {
    sc = new FS();
    out = new PrintWriter(new BufferedOutputStream(System.out), true);
    int n = sc.nextInt();
    out.println("? 1 " + n);
    int smax = sc.nextInt();
    if (smax == n) bs(1, n - 1, false);
    else if (smax == 1) bs(2, n, true);
    else {
      out.println("? 1 " + smax);
      if (sc.nextInt() == smax) bs(1, smax - 1, false);
      else bs(smax + 1, n, true);
    }
    out.close();
  }
}