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.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class GuessingTheGreatest implements Closeable {

  private InputReader in = new InputReader(System.in);
  private PrintWriter out = new PrintWriter(System.out);

  public void solve() {
    int n = in.ni();
    int pivot = ask(0, n - 1);
    int left, right;
    if (pivot > 0 && pivot < n - 1) {
      int leftHalf = ask(0, pivot);
      if (leftHalf == pivot) {
        left = 0;
        right = pivot - 1;
      } else {
        left = pivot + 1;
        right = n - 1;
      }
    } else if (pivot == n - 1) {
      left = 0;
      right = n - 2;
    } else {
      left = 1;
      right = n - 1;
    }
    int max;
    if (pivot < left) {
      max = n + 5;
      while (left <= right) {
        int mid = left + (right - left) / 2;
        int response = ask(pivot, mid);
        if (response == pivot) {
          max = Math.min(max, mid);
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }
    } else {
      max = -1;
      while (left <= right) {
        int mid = left + (right - left) / 2;
        int response = ask(mid, pivot);
        if (response == pivot) {
          max = Math.max(mid, max);
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    answer(max);
  }

  private int ask(int left, int right) {
    out.printf("? %d %d\n", left + 1, right + 1);
    out.flush();
    return in.ni() - 1;
  }

  private void answer(int idx) {
    out.printf("! %d\n", idx + 1);
    out.flush();
  }

  @Override
  public void close() throws IOException {
    in.close();
    out.close();
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int ni() {
      return Integer.parseInt(next());
    }

    public long nl() {
      return Long.parseLong(next());
    }

    public void close() throws IOException {
      reader.close();
    }
  }

  public static void main(String[] args) throws IOException {
    try (GuessingTheGreatest instance = new GuessingTheGreatest()) {
      instance.solve();
    }
  }
}