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;
#define endl "\n"
#define ll long long
#define pb(a) push_back(a)
#define arr(a) new ll int[a]
#define INF 100000000000000000
#define MOD 1000000007
#define MOD1 998244353
#define arr1(a) new arra[a]
#define str(a) new string[a]
#define all(arr,n,a) for(ll int i=0;i<=n;i++)arr[i]=a
//const int N = 1009,p=31;
//ll int pw[N],inv_pw[N],hash2[N+1],hash1[N+1],pw1[N],inv_pw1[N],hash1r[N+1],hash2r[N+1];
//ll fact[N];
//void factorial(){
//    fact[0] = fact[1] = 1;
//    for(ll i = 2; i < N; i++)
//        fact[i] = (fact[i-1] * i) % MOD;
//}
// ll power(ll a, ll b, ll mod){
// 	ll x = 1, y = a;
// 	while (b > 0){
// 		if (b%2){
// 			x = (x*y)%mod;
// 		}
// 		y = (y*y)%mod;
// 		b /= 2;
// 	}
// 	return x%mod;
// }
//ll modular_inverse(ll n, ll mod){
//	return power(n, mod-2, mod);
//}
//void precal()
//{
//    pw[0]=1;
//    pw1[0]=1;
//    inv_pw1[0]=1;
//    inv_pw[0]=1;
//    ll int temp=modular_inverse(p,MOD),temp1=modular_inverse(p,MOD1);
//    for(ll int i=1;i<N;i++)
//    {
//        pw[i]=(pw[i-1]*p)%MOD;
//        pw1[i]=(pw1[i-1]*p)%MOD1;
//        inv_pw1[i]=(inv_pw1[i-1]*temp1)%MOD1;
//        inv_pw[i]=(inv_pw[i-1]*temp)%MOD;
//    }
//}
//void build(string& s,ll int hash1[],ll int pw[],ll int mod)
//{
//    ll int n=s.size();
//    for(ll int i=1;i<=n;i++)
//    {
//        hash1[i]=(hash1[i-1]+(pw[i-1]*(s[i-1]-'a'+1))%mod)%mod;
//    }
//}
//ll int get_hash(ll int hash1[],ll int inv_pw[],ll int mod,ll int l,ll int r)
//{
//    if(l>r)return 0;
//    ll int res=(hash1[r]-hash1[l-1]+mod)%mod;
//    res=(res*inv_pw[l-1])%mod;
//    return res;
//}
//ll nCr(ll n, ll k, ll mod){
//	return (fact[n]*((modular_inverse(fact[k],MOD)*modular_inverse(fact[n-k],MOD))%mod))%mod;
//}

//struct arra{
//    ll int d=0,idx;
//}arr[200008];
//bool comp(struct arra a,struct arra b)
//{
//    return a.d>b.d;
//}
//bool comp1(pair<ll int,ll int>p1,pair<ll int,ll int>p2)
//{
//    return p1.first>p2.second;
//}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,a,t1;
    cin>>n;
    cout<<"? 1 "<<n<<endl;
    cout.flush();
    cin>>a;
    ll l=1,r=n,mid;
    if(a==1)
    {
        l++;
    }
    else if(a==n)r--;
    else{
        cout<<"? "<<a<<" "<<n<<endl;
        cout.flush();
        cin>>t1;
        if(t1==a)
        {
            l=a+1;
        }
        else r=a-1;
    }
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(mid>a){
            cout<<"? "<<a<<" "<<mid<<endl;
            cout.flush();
            cin>>t1;
            if(t1==a)r=mid;
            else l=mid+1;
        }
        else {
            cout<<"? "<<mid<<" "<<a<<endl;
            cout.flush();
            cin>>t1;
            if(t1==a)l=mid;
            else r=mid-1;
        }
    }
    if(r-l==1)
    {
        cout<<"? "<<l<<" "<<r<<endl;
        cout.flush();
        cin>>t1;
        if(l==t1)
        {
            cout<<"! "<<r<<endl;
        }
        else cout<<"! "<<l<<endl;
    }
    else cout<<"! "<<l<<endl;
    return 0;
}