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 class D {
	static class pair implements Comparable<pair> {

		int f;
		int s;
		double th;
		int id;

		public pair() {

		}

		public pair(int a, int b, int c) {
			f = a;
			s = b;
			th = (f * 1.00000) / (s * 1.00000);
			id = c;

		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			if (this.th > o.th)
				return -1;
			if (this.th == o.th) {
				return this.s - o.s;
			} else
				return 1;
		}

	}

	static int mod = (int) 1e9 + 7;
	static int ar[];
	static Scanner sc = new Scanner(System.in);
	static StringBuilder out = new StringBuilder();
	static ArrayList<Integer> grEven[];
	static ArrayList<Integer> grOdd[];

	static void sort(int a[], int n) {

		ArrayList<Integer> al = new ArrayList<>();

		for (int i = 0; i < n; i++) {

			al.add(a[i]);
		}

		Collections.sort(al);

		for (int i = 0; i < n; i++) {

			a[i] = al.get(i);
		}
	}

	static void in(int a[], int n) throws IOException {
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
	}

	public static void main(String[] args) throws IOException {
		int t = 1;// sc.nextInt();

		while (t-- > 0) {

			int n = sc.nextInt();

			int l = 1;
			int r = n;
			int ans = 0;
			System.out.println("? " + l + " " + r);
			System.out.flush();
			int max = sc.nextInt();

			if (n == 2) {

				if (max == 1)
					System.out.println("! " + 2);
				else
					System.out.println("! " + 1);
				continue;
			}
			if (max == 1) {
				l = max + 1;

			} else if (max == r) {
				r = max - 1;
			} else {
				System.out.println("? " + l + " " + max);
				System.out.flush();

				if (sc.nextInt() == max) {
					r = max - 1;
				} else {
					l = max + 1;
				}
			}
			int cnt = 2;
			if (max == l - 1) {
				cnt++;
				while (l <= r) {

					cnt++;
					int mid = (l + r) / 2;

					System.out.println("? " + max + " " + mid);

					System.out.flush();

					int m1 = sc.nextInt();

					if (m1 == max) {

						r = mid - 1;
						ans = mid;

					} else {

						l = mid + 1;

					}

				}
			} else {

				cnt++;

				while (l <= r) {

					int mid = (l + r) / 2;

					System.out.println("? " + mid + " " + max);

					System.out.flush();

					int m1 = sc.nextInt();

					if (m1 == max) {

						l = mid + 1;
						ans = mid;

					} else {

						r = mid - 1;

					}

				}

			}

			System.out.println("! " + ans);

		}

		System.out.println(out);
	}

//	static Reader sc=new Reader();
	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

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

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

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					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();
			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();
			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();
			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();
		}
	}

}