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 all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
using tp = tuple<ll, ll, ll>;

constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;

using Array = vector<ll>;
using Matrix = vector<Array>;

/*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
*/

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
    ll to, cap, rev;
    Edge(ll _to, ll _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}


void solve() {
    ll n;
    cin>>n;

    ll x;
    cout<<"? 1 "<<n<<endl;
    cin>>x;
    bool right=false;
    if(n!=x){
        cout<<"? "<<x<<" "<<n<<endl;
        ll x2;
        cin>>x2;
        if(x2==x) right=true;//xより右にある
    }
    if(right and x==n-1){
        cout<<"! "<<n<<endl;
        return;
    }else if(!right and x==2){
        cout<<"! "<<1<<endl;
        return;
    }

    if(right){
        cout<<"? "<<x<<" "<<x+1<<endl;
        ll y;
        cin>>y;
        if(y==x){
            cout<<"! "<<x+1<<endl;
            return;
        }
        ll l=x+1;
        ll r=n;
        while(l+1<r){
            ll m=l+r>>1;
            cout<<"? "<<x<<" "<<m<<endl;
            ll x2;
            cin>>x2;
            if(x==x2) r=m;
            else l=m;
        }
        cout<<"! "<<r<<endl;
    }else{
        //xより左にある
        cout<<"? "<<x-1<<" "<<x<<endl;
        ll y;
        cin>>y;
        if(y==x){
            cout<<"! "<<x-1<<endl;
            return;
        }
        ll l=1;
        ll r=x-1;
        while(l+1<r){
            ll m=l+r>>1;
            cout<<"? "<<m<<" "<<x<<endl;
            ll x2;
            cin>>x2;
            if(x==x2) l=m;
            else r=m;
        }
        cout<<"! "<<l<<endl;
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
/*
    ll t;
    cin >> t;
    REP(i, t - 1) {
        solve();
    }*/

    solve();

    return 0;
}