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<iostream>
#include <iomanip>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<b;i++)
#define it(x,b)  for(auto &x:b)
#define NUM  1000000007
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2)%NUM;
    if (b % 2)
        return (((res * res)%NUM)* a)%NUM;
    else
        return (res * res)%NUM;
}
struct prep
{
    vll fact;
    vll inv;
    ll m;
    explicit prep(int n)
    {
        ll mod=NUM;
        int num=n;
        m=mod;
        fact.resize(n+31);
        inv.resize(n+31);
        fact[0]=1;
        inv[0]=1;
        for(int i=1;i<=num+30;i++)
        {
            fact[i]=(fact[i-1]*i)%mod;
            inv[i]=binpow(fact[i],mod-2)%NUM;
        }
    }
    ll ncr(ll n , ll r)
    {
        if(r>n||r<0)
        {
            return 0;
        }
        ll p = ((fact[n]*inv[r])%m);
        p=(p*(inv[n-r])%m);
        return p;
    }
    ll fac(ll num)
    {
        return fact[num];
    }
};
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};//unordered_map<pair<long long, long long>, bool, hash_pair> um;
bool isPrime(long long n) {
    if (n == 1)return false;
    if (n == 2)return true;
    for (long long i = 2; i * i <= n; i++)
        if (n % i == 0)return false;
    return true;
}
ll min(ll a,ll b)
{
    if(a>b)
    {
        return b;
    }
    return a;
}
ll max(ll a, ll b)
{
    if(a>b)
        return a;
    return b;
}
long long dif(long long a,long long b)
{
    if(a>b)
        return a-b;
    return b-a;
}
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
    long long k=gcd(a,b);
    return (a*b)/k;
}
void read(ll arr[],long long n)
{
    for(long long i=0;i<n;i++)
    {
        cin>>arr[i];
    }
}
void addedge(vector<vector<long long>>&v,long long p1,long long p2) {
    v[p1].push_back({p2});
    v[p2].push_back({p1});
}
bool mycmp(pair<long long ,float>p1,pair<long long ,float>p2)
{
    return p1.first<p2.first;
}
void print(ll arr[],ll n)
{
    for (long long i = 0; i < n; ++i) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
vector<long long >prime;
void sieveOferatosthenes(long long  MAX)
{
    bool pri[MAX + 1];
    memset(pri, true, sizeof(pri));
    pri[1] = false;

    for (long long  p = 2; p * p <= MAX; p++) {

        // If prime[p] is not changed, then it is a prime
        if (pri[p]) {

            // Set all multiples of p to non-prime
            for (long long  i = p * 2; i <= MAX; i += p)
                pri[i] = false;
        }
    }
    for(long long  i=1;i<=MAX;i++)
    {
        if(pri[i])
        {
            prime.push_back(i);
        }
    }
}
int n;
void ask(int l,int r)
{
    if(l>=1&&r<=n) {
        cout << "?" << " " << l << " " << r << endl;
        cout.flush();
    }
}
bool check1(int p,int second)
{
    if(p==second-1)
    {
        return true;
    }
    ask(p+1,second);
    ll z;cin>>z;
    if(z!=second)
    {
        return true;
    }
    return false;
}
bool check2(int second,int p)
{
    if(p==second+1)
    {
        return true;
    }
    ask(second,p-1);
    ll z;cin>>z;
    if(z!=second)
    {
        return true;
    }
    return false;
}
void solve()
{
    n;cin>>n;
    int second;
    ask(1,n);
    cin>>second;
    map<pll,ll>m;
    m[{1,n}]=second;
    bool l=false;
    if(second!=1)
    {
        ll p;
        if(m.find({1,second})==m.end()) {
            ask(1, second);
            cin >> p;
        }
        else
        {
            p=m[{1,second}];
        }
        if(p==second)
        {
            l=true;
        }
    }
    if(l)
    {
        int high=second-1;
        int low=1;
        int mid;
        ll res;
        for(;low<=high;)
        {
            mid=(low+high)/2;
            ll p;
            if(m.find({mid,second})==m.end())
            {
                ask(mid,second);
                cin>>p;
                m[{mid,second}]=p;
            }
            else
            {
                p=m[{mid,second}];
            }
            if(p==second)
            {
                res=mid;
                low=mid+1;
            }
            else
            {
                high=mid-1;
            }
        }
        cout<<"!"<<" "<<res<<endl;
    }
    else
    {
        int high=n;
        int low=second+1;
        int mid;
        ll res;
        for(;low<=high;)
        {
            mid=(low+high)/2;
            ll p;
            if(m.find({second,mid})==m.end()) {
                ask(second, mid);
                cin >> p;
                m[{second,mid}]=p;
            }
            else
            {
                p=m[{second,mid}];
            }
            if(p==second)
            {
                res=mid;
                high=mid-1;
            }
            else
            {
                low=mid+1;
            }
        }
        cout<<"!"<<" "<<res<<endl;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;t=1;
    //cin>>t;
    // WE WILL WIN.
    while(t--)
    {
        solve();
    }
}