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 C2
{
	public static class FastIO
	{
		BufferedReader br;
		BufferedWriter bw, be;
		StringTokenizer st;

		public FastIO()
		{
			br = new BufferedReader(new InputStreamReader(System.in));
			bw = new BufferedWriter(new OutputStreamWriter(System.out));
			be = new BufferedWriter(new OutputStreamWriter(System.err));
			st = new StringTokenizer("");
		}

		private void read() throws IOException
		{
			st = new StringTokenizer(br.readLine());
		}

		public String ns() throws IOException
		{
			while(!st.hasMoreTokens())
				read();
			return st.nextToken();
		}

		public int ni() throws IOException
		{
			return Integer.parseInt(ns());
		}

		public long nl() throws IOException
		{
			return Long.parseLong(ns());
		}

		public float nf() throws IOException
		{
			return Float.parseFloat(ns());
		}

		public double nd() throws IOException
		{
			return Double.parseDouble(ns());
		}

		public char nc() throws IOException
		{
			return ns().charAt(0);
		}

		public int[] nia(int n) throws IOException
		{
			int[] a = new int[n];
			for(int i = 0; i < n; i++)
				a[i] = ni();

			return a;
		}

		public long[] nla(int n) throws IOException
		{
			long[] a = new long[n];
			for(int i = 0; i < n; i++)
				a[i] = nl();

			return a;
		}

		public char[] nca() throws IOException
		{
			return f.ns().toCharArray();
		}

		public void out(String s) throws IOException
		{
			bw.write(s);
			bw.flush();
		}

		public void flush() throws IOException
		{
			bw.flush();
			be.flush();
		}

		public void err(String s) throws IOException
		{
			be.write(s);
			be.flush();
		}
	}

	static class Pair
	{
		int a, b;

		Pair(int x, int y)
		{
			a = x;
			b = y;
		}

		public int hashCode()
		{
			return a^b;
		}

		public boolean equals(Object obj)
		{
			Pair that = (Pair)obj;

			return a == that.a && b == that.b;
		}
	}

	static FastIO f;
	static HashMap<Pair, Integer> h;

	public static void main(String args[]) throws IOException
	{
		f = new FastIO();

		int n, ans, smax;
		h = new HashMap<>();

		n = f.ni();

		smax = getSMax(1, n);

		ans = (n == 2) ? (smax == 1) ? 2 : 1 : (smax == 1 || (smax != n && smax == getSMax(smax, n))) ? getRB(smax+1, n, smax) : getLB(1, smax-1, smax);

		f.out("! " + ans + "\n");
	}

	public static int getLB(int s, int e, int sm) throws IOException
	{
		if(e == s)
			return s;

		if(e == s+1)
			return (getSMax(e, sm) == sm) ? e : s;

		int mid = s + (e-s)/2;

		int s1 = getSMax(mid+1, sm);

		if(s1 == sm)
			return getLB(mid+1, e, sm);

		return getLB(s, mid, sm);
	}

	public static int getRB(int s, int e, int sm) throws IOException
	{
		if(e == s)
			return s;

		if(e == s+1)
			return (getSMax(sm, s) == sm) ? s : e;

		int mid = s + (e-s)/2;

		int s1 = getSMax(sm, mid);

		if(s1 == sm)
			return getRB(s, mid, sm);

		return getRB(mid+1, e, sm);
	}

	public static int getMax(int l, int r, int sm) throws IOException
	{
		if(r == l+1)
			return (sm == l) ? r : l;

		if(r == l+2)
		{
			int a = getMax(l, l+1, getSMax(l, l+1)), b = getMax(l+1, r, getSMax(l+1, r));
			return (a == b || b == sm) ? a : b;
		}

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

		if(sm <= mid)
		{
			int sm1 = getSMax(l, mid);

			if(sm1 == sm)
				return getMax(l, mid, sm1);

			return getMax(mid+1, r, getSMax(mid+1, r));
		}
		else
		{
			int sm2 = getSMax(mid+1, r);
			if(sm2 == sm)
				return getMax(mid+1, r, sm2);

			return getMax(l, mid, getSMax(l, mid));
		}
	}

	public static int getSMax(int l, int r) throws IOException
	{
		Pair p = new Pair(l, r);

		if(h.containsKey(p))
			return h.get(p);

		f.out("? " + l + " " + r + "\n");
		int ans = f.ni();
		h.put(p, ans);

		return ans;
	}
}