#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
namespace io_impl {
inline bool maybe_digit(char c) { return c >= '0' && c <= '9'; }
struct io_s {
 private:
  FILE* fin = stdin;
  FILE* fout = stdout;
  bool negative;
  bool ok = true;
  char ch;
  int precious;
  long double epslion;
  char next_char() const { return fgetc(fin); }

 public:
  void init() { ch = next_char(); }
  void init(FILE* _in, FILE* _out) {
    fin = _in;
    fout = _out;
    init();
  }
  template <typename T>
  bool rn(T& _v) {
    negative = false;
    _v = 0;
    while (!maybe_digit(ch) && ch != EOF) {
      negative = ch == '-';
      ch = next_char();
    }
    if (ch == EOF) return ok = false;
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
    if (negative) _v = -_v;
    return true;
  }
  template <typename T>
  void rn_unsafe(T& _v) {
    negative = false;
    _v = 0;
    while (!maybe_digit(ch)) {
      negative = ch == '-';
      ch = next_char();
    }
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
    if (negative) _v = -_v;
  }
  template <typename T>
  T rn() {
    T v = T();
    rn_unsafe(v);
    return v;
  }
  template <typename T>
  bool run(T& _v) {
    _v = 0;
    while (!maybe_digit(ch) && ch != EOF) ch = next_char();
    if (ch == EOF) return ok = false;
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
    return true;
  }
  template <typename T>
  void run_unsafe(T& _v) {
    _v = 0;
    while (!maybe_digit(ch)) ch = next_char();
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
  }
  template <typename T>
  T run() {
    T v = T();
    run_unsafe(v);
    return v;
  }
  template <typename T>
  bool rd(T& _v) {
    negative = false;
    _v = 0;
    while (!maybe_digit(ch) && ch != EOF) {
      negative = ch == '-';
      ch = next_char();
    }
    if (ch == EOF) return ok = false;
    do {
      _v = (_v * 10) + (ch - '0');
    } while (maybe_digit(ch = next_char()));
    static int stk[70], tp;
    if (ch == '.') {
      tp = 0;
      T _v2 = 0;
      while (maybe_digit(ch = next_char())) {
        stk[tp++] = ch - '0';
      }
      while (tp--) {
        _v2 = _v2 / 10 + stk[tp];
      }
      _v += _v2 / 10;
    }
    if (ch == 'e' || ch == 'E') {
      ch = next_char();
      static bool _neg = false;
      if (ch == '+')
        ch = next_char();
      else if (ch == '-')
        _neg = true, ch = next_char();
      if (maybe_digit(ch)) {
        _v *= pow(10, run<long long>() * (_neg ? -1 : 1));
      }
    }
    if (negative) _v = -_v;
    return true;
  }
  template <typename T>
  T rd() {
    T v = T();
    rd(v);
    return v;
  }
  int gets(char* s) {
    char* c = s;
    while (ch == '\n' || ch == '\r' || ch == ' ') ch = next_char();
    if (ch == EOF) return (ok = false), *c = 0;
    do {
      *(c++) = ch;
      ch = next_char();
    } while (ch != '\n' && ch != '\r' && ch != ' ' && ch != EOF);
    *(c++) = '\0';
    return static_cast<int>(c - s - 1);
  }
  int getline(char* s) {
    char* c = s;
    while (ch == '\n' || ch == '\r') ch = next_char();
    if (ch == EOF) return (ok = false), *c = 0;
    do {
      *(c++) = ch;
      ch = next_char();
    } while (ch != '\n' && ch != '\r' && ch != EOF);
    *(c++) = '\0';
    return static_cast<int>(c - s - 1);
  }
  char get_alpha() {
    while (!isalpha(ch)) ch = next_char();
    const char ret = ch;
    ch = next_char();
    return ret;
  }
  char get_nonblank() {
    while (iswspace(ch)) ch = next_char();
    const char ret = ch;
    ch = next_char();
    return ret;
  }
  char get_char() {
    const char ret = ch;
    ch = next_char();
    return ret;
  }
  template <typename T>
  void o(T p) {
    static int stk[70], tp;
    if (p == 0) {
      putchar('0');
      return;
    }
    if (p < 0) {
      p = -p;
      putchar('-');
    }
    while (p) stk[++tp] = p % 10, p /= 10;
    while (tp) putchar(stk[tp--] + '0');
  }
  template <typename T>
  void od(T v) {
    static int stk[70], tp;
    tp = 0;
    if (fabs(v) < epslion / 10) {
      putchar('0');
      if (precious > 0) {
        putchar('.');
        for (int i = 0; i < precious; ++i) putchar('0');
      }
      return;
    }
    if (v < 0) {
      v = -v;
      putchar('-');
    }
    v += epslion / 2;
    T p = floor(v) + epslion / 10;
    while (fabs(p) > 1 - epslion) {
      stk[++tp] = fmod(p, 10), p = floor(p / 10) + epslion;
    }
    if (tp == 0) putchar('0');
    while (tp) putchar(stk[tp--] + '0');
    if (precious == 0) return;
    putchar('.');
    v -= floor(v);
    for (int i = 0; i < precious; ++i) {
      v *= 10;
      putchar((int)floor(v) + '0');
      v = fmod(v, 1);
    }
  }
  typedef void io_operator_func(io_s& v);
  typedef char* charptr;
  template <typename T>
  io_s& operator>>(T& x) {
    if (numeric_limits<T>::is_signed)
      rn(x);
    else
      run(x);
    return *this;
  }
  template <typename TFirst, typename TSecond>
  io_s& operator>>(pair<TFirst, TSecond>& pr) {
    *this >> pr.first >> pr.second;
    return *this;
  }
  template <typename T>
  io_s& operator<<(const T& x);
  io_s& operator<<(const io_operator_func*& x) {
    x(*this);
    return *this;
  }
  operator bool() const { return ok; }
  void set_precious(int x) {
    precious = x;
    epslion = pow(10, -x);
  }
  int ri() { return rn<int>(); }
  long long rll() { return rn<long long>(); }
  static void new_line(io_s& v) { putchar('\n'); }
  static void flush(io_s& v) { fflush(stdout); }
  template <typename T>
  inline void o(T begin, T end) {
    while (begin != end) {
      o(*begin++);
      o(begin == end ? '\n' : ' ');
    }
  }
};
template <>
inline io_s& io_s::operator>>(char*& x) {
  gets(x);
  return *this;
}
template <>
inline io_s& io_s::operator>>(float& x) {
  rd(x);
  return *this;
}
template <>
inline io_s& io_s::operator>>(double& x) {
  rd(x);
  return *this;
}
template <>
inline io_s& io_s::operator>>(long double& x) {
  rd(x);
  return *this;
}
template <>
inline void io_s::o(const char p) {
  putchar(p);
}
template <>
inline void io_s::o(const char* p) {
  printf(p);
}
template <>
inline void io_s::o(float p) {
  od(p);
}
template <>
inline void io_s::o(double p) {
  od(p);
}
template <>
inline void io_s::o(long double p) {
  od(p);
}
template <typename T>
io_s& io_s::operator<<(const T& x) {
  o(x);
  return *this;
}
io_s::io_operator_func* nl = io_s::new_line;
io_s::io_operator_func* fl = io_s::flush;
}  // namespace io_impl
using namespace io_impl;
io_s io;
typedef void InitFunction();
typedef bool SolveFunction(int);
struct env_s {
 private:
  bool global_inited = false;
  bool case_inited = false;

 public:
  bool once() { return global_inited ? false : (global_inited = true); }
  bool every() { return case_inited ? false : (case_inited = true); }
  InitFunction *_initOnce, *_init;
  template <InitFunction TInitOnce, InitFunction TInit>
  void configure() {
    _initOnce = TInitOnce;
    _init = TInit;
  }
  void init(bool global) {
    if (global)
      if (_initOnce != nullptr) _initOnce();
    if (_init != nullptr) _init();
  }
  void empty_init() {}
  template <SolveFunction TSolve>
  void solve_single() {
    global_inited = false;
    case_inited = false;
    init(true);
    TSolve(0);
  }
  template <SolveFunction TSolve>
  void solve_many() {
    global_inited = false;
    int T = io.ri();
    for (int cs = 1; T--; ++cs) {
      case_inited = false;
      init(cs == 1);
      if (!TSolve(cs)) break;
    }
  }
  template <SolveFunction TSolve>
  void solve_much() {
    global_inited = false;
    case_inited = false;
    for (int cs = 1; init(cs == 1), TSolve(cs); ++cs) case_inited = false;
  }
} env;
void err() { cerr << endl; }
template <typename T, typename... Args>
void err(T a, Args... args) {
  cerr << a << ' ';
  err(args...);
}
namespace solution {
void init_once() {
  srand(time(nullptr));
  io.set_precious(12);
}
void init_every() {}
const int N = 1e5 + 10;
struct Interactive {
  int cache[N];
  Interactive() { memset(cache, -1, sizeof(cache)); }
  int ask(int p) {
    if (cache[p] == -1) {
      io << "? " << p << nl << fl;
      io >> cache[p];
    }
    return cache[p];
  }
  void answer(int p) { io << "! " << p << nl << fl; }
} i;
bool solve(int _cas) {
  int n = io.ri(), m = n / 2;
  long long p = i.ask(m + 1) - i.ask(1);
  if (p == 0) {
    i.answer(1);
    return true;
  }
  if (p & 1) {
    i.answer(-1);
    return true;
  }
  int l = 1, r = m + 1;
  while (l < r) {
    int mid = l + r >> 1;
    long long q = i.ask(m + mid) - i.ask(mid);
    if (q == 0) {
      i.answer(mid);
      return true;
    }
    if (q * p < 0)
      r = mid;
    else
      l = mid;
  }
  i.answer(l);
  return true;
}
}  // namespace solution
int main() {
  io.init();
  env.configure<solution::init_once, solution::init_every>();
  env.solve_single<solution::solve>();
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

This is an interactive problem.

Imur Ishakov decided to organize a club for people who love to play the famous game «The hat». The club was visited by n students, where n is even. Imur arranged them all in a circle and held a draw to break the students in pairs, but something went wrong. The participants are numbered so that participant i and participant i + 1 (1 ≤ i ≤ n - 1) are adjacent, as well as participant n and participant 1. Each student was given a piece of paper with a number in such a way, that for every two adjacent students, these numbers differ exactly by one. The plan was to form students with the same numbers in a pair, but it turned out that not all numbers appeared exactly twice.

As you know, the most convenient is to explain the words to the partner when he is sitting exactly across you. Students with numbers i and <image> sit across each other. Imur is wondering if there are two people sitting across each other with the same numbers given. Help him to find such pair of people if it exists.

You can ask questions of form «which number was received by student i?», and the goal is to determine whether the desired pair exists in no more than 60 questions.

Input

At the beginning the even integer n (2 ≤ n ≤ 100 000) is given — the total number of students.

You are allowed to ask no more than 60 questions.

Output

To ask the question about the student i (1 ≤ i ≤ n), you should print «? i». Then from standard output you can read the number ai received by student i ( - 109 ≤ ai ≤ 109).

When you find the desired pair, you should print «! i», where i is any student who belongs to the pair (1 ≤ i ≤ n). If you determined that such pair doesn't exist, you should output «! -1». In both cases you should immediately terminate the program.

The query that contains your answer is not counted towards the limit of 60 queries.

Please make sure to flush the standard output after each command. For example, in C++ use function fflush(stdout), in Java call System.out.flush(), in Pascal use flush(output) and stdout.flush() for Python language.

Hacking

Use the following format for hacking:

In the first line, print one even integer n (2 ≤ n ≤ 100 000) — the total number of students.

In the second line print n integers ai ( - 109 ≤ ai ≤ 109) separated by spaces, where ai is the number to give to i-th student. Any two adjacent elements, including n and 1, must differ by 1 or  - 1.

The hacked solution will not have direct access to the sequence ai.

Examples

Input

8
<span class="tex-span"></span>
2
<span class="tex-span"></span>
2


Output

<span class="tex-span"></span>
? 4
<span class="tex-span"></span>
? 8
<span class="tex-span"></span>
! 4


Input

6
<span class="tex-span"></span>
1
<span class="tex-span"></span>
2
<span class="tex-span"></span>
3 
<span class="tex-span"></span>
2
<span class="tex-span"></span>
1
<span class="tex-span"></span>
0

Output

<span class="tex-span"></span>
? 1
<span class="tex-span"></span>
? 2
<span class="tex-span"></span>
? 3
<span class="tex-span"></span>
? 4
<span class="tex-span"></span>
? 5
<span class="tex-span"></span>
? 6
<span class="tex-span"></span>
! -1

Note

Input-output in statements illustrates example interaction.

In the first sample the selected sequence is 1, 2, 1, 2, 3, 4, 3, 2

In the second sample the selection sequence is 1, 2, 3, 2, 1, 0.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
namespace io_impl {
inline bool maybe_digit(char c) { return c >= '0' && c <= '9'; }
struct io_s {
 private:
  FILE* fin = stdin;
  FILE* fout = stdout;
  bool negative;
  bool ok = true;
  char ch;
  int precious;
  long double epslion;
  char next_char() const { return fgetc(fin); }

 public:
  void init() { ch = next_char(); }
  void init(FILE* _in, FILE* _out) {
    fin = _in;
    fout = _out;
    init();
  }
  template <typename T>
  bool rn(T& _v) {
    negative = false;
    _v = 0;
    while (!maybe_digit(ch) && ch != EOF) {
      negative = ch == '-';
      ch = next_char();
    }
    if (ch == EOF) return ok = false;
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
    if (negative) _v = -_v;
    return true;
  }
  template <typename T>
  void rn_unsafe(T& _v) {
    negative = false;
    _v = 0;
    while (!maybe_digit(ch)) {
      negative = ch == '-';
      ch = next_char();
    }
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
    if (negative) _v = -_v;
  }
  template <typename T>
  T rn() {
    T v = T();
    rn_unsafe(v);
    return v;
  }
  template <typename T>
  bool run(T& _v) {
    _v = 0;
    while (!maybe_digit(ch) && ch != EOF) ch = next_char();
    if (ch == EOF) return ok = false;
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
    return true;
  }
  template <typename T>
  void run_unsafe(T& _v) {
    _v = 0;
    while (!maybe_digit(ch)) ch = next_char();
    do {
      _v = (_v << 1) + (_v << 3) + ch - '0';
    } while (maybe_digit(ch = next_char()));
  }
  template <typename T>
  T run() {
    T v = T();
    run_unsafe(v);
    return v;
  }
  template <typename T>
  bool rd(T& _v) {
    negative = false;
    _v = 0;
    while (!maybe_digit(ch) && ch != EOF) {
      negative = ch == '-';
      ch = next_char();
    }
    if (ch == EOF) return ok = false;
    do {
      _v = (_v * 10) + (ch - '0');
    } while (maybe_digit(ch = next_char()));
    static int stk[70], tp;
    if (ch == '.') {
      tp = 0;
      T _v2 = 0;
      while (maybe_digit(ch = next_char())) {
        stk[tp++] = ch - '0';
      }
      while (tp--) {
        _v2 = _v2 / 10 + stk[tp];
      }
      _v += _v2 / 10;
    }
    if (ch == 'e' || ch == 'E') {
      ch = next_char();
      static bool _neg = false;
      if (ch == '+')
        ch = next_char();
      else if (ch == '-')
        _neg = true, ch = next_char();
      if (maybe_digit(ch)) {
        _v *= pow(10, run<long long>() * (_neg ? -1 : 1));
      }
    }
    if (negative) _v = -_v;
    return true;
  }
  template <typename T>
  T rd() {
    T v = T();
    rd(v);
    return v;
  }
  int gets(char* s) {
    char* c = s;
    while (ch == '\n' || ch == '\r' || ch == ' ') ch = next_char();
    if (ch == EOF) return (ok = false), *c = 0;
    do {
      *(c++) = ch;
      ch = next_char();
    } while (ch != '\n' && ch != '\r' && ch != ' ' && ch != EOF);
    *(c++) = '\0';
    return static_cast<int>(c - s - 1);
  }
  int getline(char* s) {
    char* c = s;
    while (ch == '\n' || ch == '\r') ch = next_char();
    if (ch == EOF) return (ok = false), *c = 0;
    do {
      *(c++) = ch;
      ch = next_char();
    } while (ch != '\n' && ch != '\r' && ch != EOF);
    *(c++) = '\0';
    return static_cast<int>(c - s - 1);
  }
  char get_alpha() {
    while (!isalpha(ch)) ch = next_char();
    const char ret = ch;
    ch = next_char();
    return ret;
  }
  char get_nonblank() {
    while (iswspace(ch)) ch = next_char();
    const char ret = ch;
    ch = next_char();
    return ret;
  }
  char get_char() {
    const char ret = ch;
    ch = next_char();
    return ret;
  }
  template <typename T>
  void o(T p) {
    static int stk[70], tp;
    if (p == 0) {
      putchar('0');
      return;
    }
    if (p < 0) {
      p = -p;
      putchar('-');
    }
    while (p) stk[++tp] = p % 10, p /= 10;
    while (tp) putchar(stk[tp--] + '0');
  }
  template <typename T>
  void od(T v) {
    static int stk[70], tp;
    tp = 0;
    if (fabs(v) < epslion / 10) {
      putchar('0');
      if (precious > 0) {
        putchar('.');
        for (int i = 0; i < precious; ++i) putchar('0');
      }
      return;
    }
    if (v < 0) {
      v = -v;
      putchar('-');
    }
    v += epslion / 2;
    T p = floor(v) + epslion / 10;
    while (fabs(p) > 1 - epslion) {
      stk[++tp] = fmod(p, 10), p = floor(p / 10) + epslion;
    }
    if (tp == 0) putchar('0');
    while (tp) putchar(stk[tp--] + '0');
    if (precious == 0) return;
    putchar('.');
    v -= floor(v);
    for (int i = 0; i < precious; ++i) {
      v *= 10;
      putchar((int)floor(v) + '0');
      v = fmod(v, 1);
    }
  }
  typedef void io_operator_func(io_s& v);
  typedef char* charptr;
  template <typename T>
  io_s& operator>>(T& x) {
    if (numeric_limits<T>::is_signed)
      rn(x);
    else
      run(x);
    return *this;
  }
  template <typename TFirst, typename TSecond>
  io_s& operator>>(pair<TFirst, TSecond>& pr) {
    *this >> pr.first >> pr.second;
    return *this;
  }
  template <typename T>
  io_s& operator<<(const T& x);
  io_s& operator<<(const io_operator_func*& x) {
    x(*this);
    return *this;
  }
  operator bool() const { return ok; }
  void set_precious(int x) {
    precious = x;
    epslion = pow(10, -x);
  }
  int ri() { return rn<int>(); }
  long long rll() { return rn<long long>(); }
  static void new_line(io_s& v) { putchar('\n'); }
  static void flush(io_s& v) { fflush(stdout); }
  template <typename T>
  inline void o(T begin, T end) {
    while (begin != end) {
      o(*begin++);
      o(begin == end ? '\n' : ' ');
    }
  }
};
template <>
inline io_s& io_s::operator>>(char*& x) {
  gets(x);
  return *this;
}
template <>
inline io_s& io_s::operator>>(float& x) {
  rd(x);
  return *this;
}
template <>
inline io_s& io_s::operator>>(double& x) {
  rd(x);
  return *this;
}
template <>
inline io_s& io_s::operator>>(long double& x) {
  rd(x);
  return *this;
}
template <>
inline void io_s::o(const char p) {
  putchar(p);
}
template <>
inline void io_s::o(const char* p) {
  printf(p);
}
template <>
inline void io_s::o(float p) {
  od(p);
}
template <>
inline void io_s::o(double p) {
  od(p);
}
template <>
inline void io_s::o(long double p) {
  od(p);
}
template <typename T>
io_s& io_s::operator<<(const T& x) {
  o(x);
  return *this;
}
io_s::io_operator_func* nl = io_s::new_line;
io_s::io_operator_func* fl = io_s::flush;
}  // namespace io_impl
using namespace io_impl;
io_s io;
typedef void InitFunction();
typedef bool SolveFunction(int);
struct env_s {
 private:
  bool global_inited = false;
  bool case_inited = false;

 public:
  bool once() { return global_inited ? false : (global_inited = true); }
  bool every() { return case_inited ? false : (case_inited = true); }
  InitFunction *_initOnce, *_init;
  template <InitFunction TInitOnce, InitFunction TInit>
  void configure() {
    _initOnce = TInitOnce;
    _init = TInit;
  }
  void init(bool global) {
    if (global)
      if (_initOnce != nullptr) _initOnce();
    if (_init != nullptr) _init();
  }
  void empty_init() {}
  template <SolveFunction TSolve>
  void solve_single() {
    global_inited = false;
    case_inited = false;
    init(true);
    TSolve(0);
  }
  template <SolveFunction TSolve>
  void solve_many() {
    global_inited = false;
    int T = io.ri();
    for (int cs = 1; T--; ++cs) {
      case_inited = false;
      init(cs == 1);
      if (!TSolve(cs)) break;
    }
  }
  template <SolveFunction TSolve>
  void solve_much() {
    global_inited = false;
    case_inited = false;
    for (int cs = 1; init(cs == 1), TSolve(cs); ++cs) case_inited = false;
  }
} env;
void err() { cerr << endl; }
template <typename T, typename... Args>
void err(T a, Args... args) {
  cerr << a << ' ';
  err(args...);
}
namespace solution {
void init_once() {
  srand(time(nullptr));
  io.set_precious(12);
}
void init_every() {}
const int N = 1e5 + 10;
struct Interactive {
  int cache[N];
  Interactive() { memset(cache, -1, sizeof(cache)); }
  int ask(int p) {
    if (cache[p] == -1) {
      io << "? " << p << nl << fl;
      io >> cache[p];
    }
    return cache[p];
  }
  void answer(int p) { io << "! " << p << nl << fl; }
} i;
bool solve(int _cas) {
  int n = io.ri(), m = n / 2;
  long long p = i.ask(m + 1) - i.ask(1);
  if (p == 0) {
    i.answer(1);
    return true;
  }
  if (p & 1) {
    i.answer(-1);
    return true;
  }
  int l = 1, r = m + 1;
  while (l < r) {
    int mid = l + r >> 1;
    long long q = i.ask(m + mid) - i.ask(mid);
    if (q == 0) {
      i.answer(mid);
      return true;
    }
    if (q * p < 0)
      r = mid;
    else
      l = mid;
  }
  i.answer(l);
  return true;
}
}  // namespace solution
int main() {
  io.init();
  env.configure<solution::init_once, solution::init_every>();
  env.solve_single<solution::solve>();
  return 0;
}

```