Задача "Одинокое число"

def ask(x):
    global ans
    print('?', x, flush=True)
    ansL = input()
    print('?', x+1, flush=True)
    ansR = input()
    if ansL == ansR:
        return 1
    else:
        ans = ansL
        return -1
 
n = int(input())
 
if n==1:
    print('?', 1, flush=True)
    ans = input()
 
if n==3:
    print('?', 1, flush=True)
    ans1 = input()
    print('?', 2, flush=True)
    ans2 = input()
    print('?', 3, flush=True)
    ans3 = input()
    if ans1<ans2:
        ans=ans1
    if ans3>ans2:
        ans=ans3
if n>3:
    left = 1
    right = n
    while (right - left > 0):
        x = (left + right) // 2
        if x % 2 == 0:
            x += 1
        if ask(x) == -1: # загаданное число меньше x
            right = x - 1
        else: # загаданное число больше x
            left = x + 1
        # print ('left=',left)
        # print ('right=',right)
print ('!', ans)

result = 0
for _ in range(int(input())):
    result ^= int(input())
print(result)

n=int(input())
a=[]
for i in range(1,n+1):
    print(f'?{i} ',end='')
    a.append(int(input()))
for i in range(0,n,2):
    if i==n-1 or a[i]!=a[i+1]:
        print(f'!{a[i]}')
        break

result = 0
for i in range(int(input())):
    result ^= int(input(f"? {i + 1} "))
print("!", result)

n=int(input())
for i in range(n):
    a=int(input(f'?{i+1} '))
    if i%2 and a!=b or i==n-1:
        print(f'!{a if i==n-1 else b}')
        break
    b=a

for i in range(42):
    a=int(input(f'?{i+1} '))
    if i%2 and a!=b:
        print(f'!{b}')
        break
    b=a