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 CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=200005;
int prime[1100000],primesize;
bool isprime[11000000];
ll f[N],invf[N];
ll inv[N];
void getlist(int listsize){
    memset(isprime,1,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=listsize;i++){
        if(isprime[i])prime[++primesize]=i;
         for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
}
void extend_gcd(ll a, ll b, ll& d, ll& x, ll& y)
{
	if(!b){ d = a; x = 1; y = 0; }
	else { extend_gcd(b, a%b,d, y, x); y -= x*(a/b);}
}
void ni(int n)
{
	inv[0] = inv[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		inv[i] = (mod - (mod/i))*inv[mod%i]%mod;
	}
}
ll fpow(ll a,ll k){
    ll res=1;
    while(k){
        if(k&1) res=(res*a)%mod;
        k>>=1;
        a=a*a%mod;
        //cout<<1<<endl;
    }
    return res;
}
void init(int n){
    f[0]=1;
    for(int i=1;i<=n;++i){
        f[i]=f[i-1]*i%mod;
    }
    invf[n]=fpow(f[n],mod-2);
    for(int i=n-1;i>=0;--i){
        invf[i]=invf[i+1]*(i+1)%mod;
    }
}
ll C(int n,int k){
    if(k<0 || k>n) return 0;
    return f[n]*invf[k]%mod*invf[n-k]%mod;
}
int q(int l,int r)
{
	ll cnt;
    cout<<'?'<<" "<<l<<" "<<r<<endl;
 	cin>>cnt;
    return cnt;
}
void solve(){
	int n; 
	cin>>n;
    int lst=q(1,n);
    if (n==2) {
    	cout<<"!"<<" "<<(1^n^lst)<<endl;
    	return ;
    }
    ll l,r,ans=0,mid;
	ll res=(lst==1)?0:q(1,lst);
    if (res==lst)
    {
    	for(l=1,r=lst-1; mid=(l+r>>1),l<=r;){
	        if (mid>=lst) break;
	       	if (q(mid,lst)==lst) 
			   ans=mid,l=mid+1;
	       	else 
			   r=mid-1;
    	}
    }
    else 
    {
    	for(l=lst+1,r=n; mid=(l+r>>1),l<=r;){
	        if (lst>=mid) break;
	        if (q(lst,mid)==lst) 
				ans=mid,r=mid-1;
	        else 
				l=mid+1;
    	}
    }
    cout<<"!"<<" "<<ans<<endl;
   // cout.flush();
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
//	getlist(1e7);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}