solution

$n \equiv 0 \pmod{4}$ であることと目的の対が存在することは同値。 対の位置を見付けるのはいい感じに二分探索。 二分探索。

note

$n \equiv 0 \pmod{4}$ の条件は実験で出したので未証明。 二分探索が常に上手くいくことも未証明。 editorialまだですか。

implementation

#!/usr/bin/env python3
import sys
def ask(i):
    print('?', i + 1)
    sys.stdout.flush()
    a_i = int(input())
    return a_i
def answer(i):
    print('!', i + 1 if i != -1 else -1)
    sys.exit()

def has_intersection(l1, r1, l2, r2):
    if l1 <= l2 and r2 <= r1:
        return True
    if l2 <= l1 and r1 <= r2:
        return True
    return False

n = int(input())
assert n >= 2 and n % 2 == 0
if (n // 2) % 2 == 1:
    answer(-1)
else:
    assert n % 4 == 0
    l1 = 0
    r1 = n // 2
    a_l1 = ask(l1)
    a_r1 = ask(r1)
    if a_l1 == a_r1:
        answer(0)
    a_l2 = a_r1
    a_r2 = a_l1
    # print('binary search [', l1, ',', r1, ') ->', (l1 + r1) // 2, file=sys.stderr)
    while True:
        m1 = (l1 + r1) // 2
        m2 = (m1 + n // 2) % n
        a_m1 = ask(m1)
        a_m2 = ask(m2)
        if a_m1 == a_m2:
            answer(m1)
        if has_intersection(a_l1, a_m1, a_l2, a_m2):
            r1 = m1
            a_r1 = a_m1
            a_r2 = a_m2
        else:
            assert has_intersection(a_m1, a_r1, a_m2, a_r2)
            l1 = m1
            a_l1 = a_m1
            a_l2 = a_m2
        # print('binary search [', l1, ',', r1, ') ->', (l1 + r1) // 2, file=sys.stderr)
assert False

#!/usr/bin/env python3
import sys
import random
a = [ 1 ]
while True:
    if a[-1] >= -10 and random.random() < 0.5 + a[-1] / 100:
        a += [ a[-1] - 1 ]
    else:
        a += [ a[-1] + 1 ]
    if a[-1] == 0 and len(a) >= 60 and len(a) % 4 == 0:
        break
k = random.randrange(len(a))
a = a[k :] + a[: k]
# a = [1, 0, -1, -2, -1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2]
# a = [3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 4, 3, 2]
# a = a = [8, 9, 8, 7, 6, 5, 6, 5, 6, 5, 6, 7, 6, 7, 6, 5, 4, 3, 2, 3, 2, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 3, 2, 3, 2, 3, 4, 5, 6, 5, 6, 7, 8, 9, 8, 7, 6, 7]
n = len(a)
print('[*] n =', n, file=sys.stderr)
print('[*] a =', a, file=sys.stderr)

print(len(a))
sys.stdout.flush()
for _ in range(61):
    c, i = input().split()
    print('[>]', c, i, file=sys.stderr)
    i = int(i) - 1
    if c == '?':
        print(a[i])
        sys.stdout.flush()
        print('[<]', a[i], file=sys.stderr)
    elif c == '!':
        if i == -2:
            for j in range(n):
                assert a[j] != a[(j + n // 2) % n]
        else:
            assert a[i] == a[(i + n // 2) % n]
        break
    else:
        assert False
else:
    assert False