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 Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer tok;
	public static void main(String[] args) throws Exception {
		solution();
	}
	public static void solution() throws Exception {
//		arr = new int[]{9,1,2,3,4,10,5,6,7,8};
//		int n = arr.length;
		
		int n = Integer.parseInt(rd.readLine());
		
		int res = sol_rec(1,n);
		System.out.println("! "+res);
	}
	public static int sol_rec(int left, int right) throws Exception {
		
		int Mid = sol_query(left,right);
		int fMid = -1, fLeft = left, fRight = Mid-1;
		// 첫번째로 중간값을 찾는다.
		
		if(Mid > left) fMid = sol_query(left,Mid);
		// 찾은 중간값이 맨 왼쪽값이 아니라면, 왼쪽값중에 최댓값이 있는지 탐색한다.
		while(fMid == Mid) {
			// 최댓값이 있는경우 왼쪽값 내부로 탐색한다.
			int gLeft = fLeft;
			fLeft = (fLeft + fRight)/2;
			// 이진탐색을 위하여 기준값을 절반으로 나눈다.
			fMid = sol_query(fLeft, Mid);
			// 해당 절반값에 최댓값이 존재하는지 확인한다.
			if(fMid != Mid) {
				// 절반값에 없다면 절반값 바깥쪽에 있는 것이므로 바깥쪽의 재차 절반체크를 위해 값을 조정한다.
				fRight = fLeft-1;
				fLeft = gLeft;
				fMid = Mid;
			}
			if(fRight == fLeft) return fLeft;
			else if (fRight - fLeft <= 1) return sol_res2(fLeft,fRight);
			// 값이 줄어들어서 특정할 수 있게되면 출력한다.
		}
		fLeft = Mid+1;
		fRight = right;
		while(true) {
			int gRight = fRight;
			fRight = (fLeft+fRight)/2;
			fMid = sol_query(Mid, fRight);
			if(fMid != Mid) {
				fLeft = fRight+1;
				fRight = gRight;
				fMid = Mid;
			}
			if(fRight == fLeft) return fLeft;
			else if(fRight - fLeft <= 1) return sol_res2(fLeft,fRight);
		}
	}
	public static int sol_query(int left, int right) throws Exception {
		System.out.println("? "+left +" "+right);
		System.out.flush();
		return Integer.parseInt(rd.readLine());
		
//		System.out.println(left+" "+right);
//		int[] copy = new int[right-left+1];
//		int copc = 0;
//		for(int i=left-1;i<right;i++) copy[copc++] = arr[i];
//		Arrays.sort(copy);
//		int sec = copy[copy.length-2];
//		for(int i=left-1;i<right;i++) {
//			if( sec == arr[i]) return i+1;
//		}
//		return -1;
	}
	public static int sol_res2(int left, int right) throws Exception {
		int q = sol_query(left,right);
		return q == left ? right : left;
	}
	static int[] arr;
	
}