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 <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <list> 
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <string>
#include <fstream>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <stack>
#include <queue>

using namespace std;

/**********************************************************************************/

#define mod 1000000007
#define mod2 998244353
const double pi = acos(-1);
#define gcd __gcd
#define inf 1e18
// #define inf 1e9
#define ll long long
#define ld  long double
#define fl(i,a,n) for(ll i=a;i<n;i++)
#define lf(i,a,n) for(ll i=n-1;i>=a;i--)
#define read(n) ll n; cin>>n;
#define scan(a,n) vector<ll> a(n); for(ll i=0;i<n;i++) cin>>a[i];
#define print(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout<<endll;
#define p(n) cout<<n<<endll;

#define endll "\n"
#define pb push_back
#define mp make_pair
#define dec(n) fixed<<setprecision(n)
#define F first
#define S second
#define I insert
#define E end()
#define B begin()

#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define reverseall(x) reverse(all(x))

typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef map<ll,ll> mll;
typedef vector<pll> vpl;
/*************************************[DEBUG]**************************************/

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

/***********************************[FUNCTIONS]************************************/

// bitset<200000>vis(0);
vector<bool> prime;
 
void primes(ll n)
{
    prime.resize(n+1);
    prime.assign(n+1,true);
    prime[0]=0;
    prime[1]=0;
    for(ll i=2; i*i<=n; i++)
    {
        if(prime[i])
        {
            for(ll j=(i*i); j<n; j=j+i) prime[j]=false;
        }
    }
}
 
ll powM(ll x, ll y, ll m)
{
    ll ans=1, r=1;
    x=x%m;
    while(r>0 && r<=y)
    {
        if(r & y)
        {
            ans=ans*x;
            ans=ans%m;
        }
        r=r<<1;
        x=x*x;
        x=x%m;
    }
    return ans;
}

ll powN(ll a,ll n)
{
    if(n==0) return 1;
    if(n==1) return a;
    ll u=powN(a,n/2);
    u=u*u;
    if(n%2) u=u*a;
    return u;
}

ll modinv(ll a,ll m)
{
    return powM(a,m-2,m);
}

ll ncr(ll n, ll r, ll m)
{
    if(n<r) return 0;
    if(n==r || r==0) return 1;
    if(r==1) return n;
    if(n-r<r) return ncr(n,n-r,m);
    ll a=n;
    ll b=r;
    for(ll i=1; i<r; i++)
    {
        a=(a*(n-i))%m;
        b=(b*(r-i))%m;
    }
    b=modinv(b,m);
    a=(a*b)%m;
    return a;
}

/************************************[CODE]****************************************/

int query(int l, int r)
{
    cout << "? " << l + 1 << " " << r + 1 << endl;
    int x;
    cin >> x;
    return x - 1;
}

void found(int x)
{
    cout << "! " << x << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    ll p = query(0, n - 1);
    ll llv = 0, lrv = p, rlv = p + 1, rrv = n;
    for (ll it = 0; it < 18; it++) {
        ll lmv = (llv + lrv) / 2;
        ll rmv = (rlv + rrv) / 2;
        
        
        lmv = max(0LL, lmv);
        rmv = min(rmv, (ll)n - 1);
        ll v = query(lmv, rmv);
        
        if (v == p) {
            if (llv < lrv) llv = lmv + 1;
            if (rlv < rrv) rrv = rmv;
        } else {
            if (llv < lrv) lrv = lmv;
            if (rlv < rrv) rlv = rmv + 1;
        }
    }
    
    llv = max(0LL, llv);
    rlv = min((ll)n - 1, rlv);
    if (llv == rlv || query(llv, rlv) == p) cout << "! " << rlv + 1 << endl;
    else cout << "! " << llv << endl;
    return 0;
}