Problem:
 Score : 500 points    Problem Statement This is an interactive task.  Let N be an odd number at least 3 .  There are N seats arranged in a circle.
The seats are numbered 0 through N-1 .
For each i ( 0 ≤ i ≤ N - 2 ), Seat i and Seat i + 1 are adjacent.
Also, Seat N - 1 and Seat 0 are adjacent.  Each seat is either vacant, or oppupied by a man or a woman.
However, no two adjacent seats are occupied by two people of the same sex.
It can be shown that there is at least one empty seat where N is an odd number at least 3 .  You are given N , but the states of the seats are not given.
Your objective is to correctly guess the ID number of any one of the empty seats.
To do so, you can repeatedly send the following query:   Choose an integer i ( 0 ≤ i ≤ N - 1 ). If Seat i is empty, the problem is solved. Otherwise, you are notified of the sex of the person in Seat i .   Guess the ID number of an empty seat by sending at most 20 queries.      Constraints  N is an odd number.  3 ≤ N ≤ 99  999       Input and Output First, N is given from Standard Input in the following format:  N   Then, you should send queries.
A query should be printed to Standart Output in the following format.
Print a newline at the end.  i   The response to the query is given from Standard Input in the following format:  s   Here, s is Vacant , Male or Female .
Each of these means that Seat i is empty, occupied by a man and occupied by a woman, respectively.      Notice  Flush Standard Output each time you print something. Failure to do so may result in TLE .  Immediately terminate the program when s is Vacant . Otherwise, the verdict is indeterminate.  The verdict is indeterminate if more than 20 queries or ill-formatted queries are sent.        Sample Input / Output 1  In this sample, N = 3 , and Seat 0 , 1 , 2 are occupied by a man, occupied by a woman and vacant, respectively.    Input Output    3  0  Male  1  Female  2  Vacant

Solution (Python):
import sys
n = int(input())
print(0)
sys.stdout.flush()
LS = input()
if LS == 'Vacant':
    exit()
print(n-1)
sys.stdout.flush()
if input() == 'Vacant':
    exit()
L = 0
R = n-1
while L != R-1:
    M = (L+R)//2
    if M & 1:
        M += 1
    if M == R:
        M -= 1
    print(M)
    sys.stdout.flush()
    s = input()
    if s == 'Vacant':
        exit()

    if LS == s:
        L = M
    else:
        R = M

Solution (Python):
N=int(input())

print(0,flush=True)
init=input()
if init=="Vacant":
    exit()
print(N-1,flush=True)
ende=input()
if ende=="Vacant":
    exit()

cnt=2
s=0
e=N-1

while cnt<=19:

    c= (s+e)//2
    leng_sc = c-s
    leng_ce = e-c
    print(c,flush=True)
    tmp=input()
    if tmp=="Vacant":
        exit()
    else:        
        if (leng_sc%2==0 and tmp!=init) or (leng_sc%2==1 and tmp==init):
            e = c
            ende = tmp
        else:
            s = c
            init = tmp

    cnt+=1

Solution (Python):
n = int(input())

print(0)
s = str(input())
if s == 'Vacant':
    exit()
s0 = s

print(n-1)
s = str(input())
if s == 'Vacant':
    exit()

def is_ok(x):
    print(x)
    s = str(input())
    if s == 'Vacant':
        exit()
    if x%2 == 1:
        if s != s0:
            return False
        else:
            return True
    else:
        if s == s0:
            return False
        else:
            return True


l = 0
r = n-1
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c

Solution (Python):
n = int(input())
print(0)
even = input()
if even == "Vacant":
  exit()
elif even == "Male":
  odd = "Female"
else:
  odd = "Male"
print(n-1)
d = input()
if d == "Vacant":
  exit()
left = 1
right = n-2
nex = (left+right)//2
while(True):
  print(nex)
  d = input()
  if d == "Vacant":
    exit()
  if (nex%2==0 and d == even) or (nex%2 == 1 and d == odd):
    left = nex + 1
  else:
    right = nex -1
  nex = (left+right)//2

Solution (Python):
N = int(input())
ss = 0
se = N-1
print(ss,'\n')
sf = input()
if sf == 'Vacant':
    exit(0)
while True:
    if se - ss == 1:
        q = se
    else:   
        q=(ss+se)//2
    print(q,'\n')
    s = input()
    if s == 'Vacant':
        exit(0)
    elif (s == sf and (q-ss+1)%2==1 ) or (not s == sf and (q-ss+1)%2==0):
        ss = q
        sf = s
    else:
        se = q

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    

    N = int(input())
    
    
    
    
    print(0)
    sys.stdout.flush()
    s=input()
    if s=='Vacant':
        return 
    if s=='Male':
        ini=0
    else:
        ini=1

    def hantei(mid,ini,val):
        if mid%2==1:
            ini=(~ini)&1
        if val==ini:
            return 1
        else:
            return 0

    start=0
    end=N-1
    while end-start>1:
        mid=(end+start)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':
            return 
        if s=='Male':
            flag=hantei(mid,ini,0)
        else:
            flag=hantei(mid,ini,1)
        if flag:
            start=mid
        else:
            end=mid
    print(start)
    sys.stdout.flush()
    s=input()
    if s=='Vacant':
        return 
    print(end)
    sys.stdout.flush()
    s=input()
    if s=='Vacant':
        return 


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())

l = 0
r = N
last = 2
c = 0
while True:
    print(c)
    situ = input()
    if situ == "Male":
        situ = 0
    elif situ == "Female":
        situ = 1
    else:
        break
    
    if last == 2:
        last = situ
        c = N // 2
        continue
    elif (last + situ + c) % 2 == 0:
        l = c
    else:
        r = c
    c = (r+l) // 2

Solution (Python):
n = int(input())
l = 0
r = n-1

def get(i):
	print(i)
	s = input()
	if s == 'Vacant':
		exit()
	return s


def kind(i):
	return (i%2) ^ (get(i)=='Male')


kl = kind(l)
kr = kind(r)

while True:
	m = (l+r)//2
	km = kind(m)
	if km==kl:
		l, kl = m, km
	else:
		r, kr = m, km

Solution (Python):
def main():
    N = int(input())

    n_min = 0
    n_max = N-1

    print(n_min)
    tmp_min = input()
    if tmp_min == 'Vacant':
        exit()

    print(n_max)
    tmp_max = input()
    if tmp_max == 'Vacant':
        exit()

    while True:
        n_mid = (n_min + n_max) // 2
        print(n_mid)
        tmp_mid = input()
        if tmp_mid == 'Vacant':
            exit()
        if (n_mid - n_min) % 2 == 0:
            if tmp_min == tmp_mid:
                n_min = n_mid
                tmp_min = tmp_mid
            else:
                n_max = n_mid
                tmp_max = tmp_mid
        else:
            if tmp_min == tmp_mid:
                n_max = n_mid
                tmp_max = tmp_mid
            else:
                n_min = n_mid
                tmp_min = tmp_mid


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
M = 18
left = 0
right = N-1
print(left)
l = input()
if l != "Vacant":
  print(right)
  r = input()
  if r != "Vacant":
    notOK = True
    while notOK:
      middle = (right+left)//2
      print(middle)
      s = input()
      if s == "Vacant":
        notOK = False
        break
      elif (middle-left)%2 == 0 and l != s:
        right = middle
        r = s
      elif (middle-left)%2 == 1 and l == s:
        right = middle
        r = s
      else:
        left=middle
        l = s

Solution (Python):
import sys
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    i = 0
    print(i, flush=True)
    s = input()

    f = s
    first, last = 0, N

    while s != 'Vacant':
        i = (first + last)//2
        print(i, flush=True)
        s = input()
        if s == 'Vacant': break
        if (i%2 == 0 and f == s) or (i%2 == 1 and f != s): first = i
        else: last = i
    return

if __name__ == '__main__':
    main()
    sys.exit(0)

Solution (Python):
n = int(input())
print(0)
s = input()
if s == "Vacant":
    exit()
a = s
l = 0
r = n
while True:
    m = (l + r) // 2
    print(m)
    s = input()
    if s == "Vacant":
        exit()
    if (s == a) ^ ((m - l) % 2 == 1):
        l = m
        a = s
    else:
        r = m

Solution (Python):
from math import ceil
N = int(input())
cnt = 1
print(0)
S = input()
if S == 'Vacant':
    exit()
d = {'Male': 1, 'Female': 0}
sex = [-1,-1]
sex[0] = d[S]
l = 0
r = N-1
print(r)
S = input()
if S == 'Vacant':
    exit()
sex[1] = d[S]
while True:
    mid = (l+r)//2
    if mid % 2 !=0 and r-l > 2:
        mid -= 1
    print(mid)
    S = input()
    if S == 'Vacant':
        exit()
    if d[S] == sex[0]:
        l = mid
    else:
        r = mid

Solution (Python):
N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    
    ng = -1  
    ok = N  

    
    
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Solution (Python):
MALE = 0
FEMALE = 1

def query(i):
    print(i, flush=True)
    s = input()
    if s == 'Vacant':
        exit()

    if s == 'Male':
        return(MALE)
    else:
        return(FEMALE)

def search(start, end, start_gendar):
    i = (end - start)//2
    g = query(start + i)
    if (i%2 == 0 and g != start_gendar) or (i%2 != 0 and g == start_gendar):
        return (start, start+i, start_gendar)
    return (start+i, end, g)

def main():
    n = int(input())
    start = 0
    end = n
    gendar = query(0)
    for i in range(20):
        start_new, end_new, gendar_new = search(start, end, gendar)
        start = start_new
        end = end_new
        gendar = gendar_new

if __name__ == "__main__":
    main()

Solution (Python):
import sys

N = int(input())
p2 = [pow(2,i) for i in range(17) if pow(2,i) <= (N-1)]
m = max(p2)
print('0\n')
s = input()
if s == 'Vacant':
    sys.exit()
elif s == 'Male':
    search = 'F'
else:
    search = 'M'
print('{}\n'.format(m))
s = input()
if s == 'Vacant':
    sys.exit()
elif s == 'Male':
    if search == 'M':
        left = 0
        right = m
    else:
        right = N-1
        left = N-1-m
        print('{}\n'.format(right))
        s = input()
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            search = 'rF'
        else:
            search = 'rM'
else:
    if search == 'F':
        left = 0
        right = m
    else:
        right = N-1
        left = N-1-m
        print('{}\n'.format(right))
        s = input()
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            search = 'rF'
        else:
            search = 'rM'
while True:
    mid = (left+right) // 2
    print('{}\n'.format(mid))
    s = input()
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        if search == 'M':
            right = mid
        elif search == 'rF':
            right = mid
        elif search == 'rM':
            left = mid
        else:
            left = mid
    else:
        if search == 'F':
            right = mid
        elif search == 'rF':
            left = mid
        elif search == 'rM':
            right = mid
        else:
            left = mid

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
r = N-1
l = 0
print(0)
s = input()
cnt = 0
mid = (r+l)//2
if s == "Male":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Male" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Female" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2
        
elif s == "Female":
    for _ in range(25):
        print(mid)
        s = input()
        if s == "Female" and mid % 2 == 0:
            l += max((r-l)//2,1)
        elif s == "Male" and mid % 2 != 0:
            l += max((r-l)//2,1)
        elif s == "Vacant":
            break
        else:
            r -= max((r-l)//2,1)
        mid = (r+l)//2

Solution (Python):
N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x

Solution (Python):
n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

Solution (Python):
def get_sex(i):
    print(i, flush=True)
    return input()


def solve(N):
    if N <= 19:
        for i in range(N):
            print(i, flush=True)
            s = input()
            if s == 'Vacant':
                exit()

    low_sex = get_sex(0)
    if low_sex == 'Vacant':
        exit()
    high_sex = get_sex(N - 1)
    if high_sex == 'Vacant':
        exit()

    high, low = N - 1, 0
    while high > low:
        mid = (high + low) // 2
        mid_sex = get_sex(mid)
        if mid_sex == 'Vacant':
            exit()

        if (mid - low) % 2 == 1:
            if mid_sex != low_sex:
                low = mid
                low_sex = mid_sex
            else:
                high = mid
                high_sex = mid_sex
        else:
            if mid_sex != low_sex:
                high = mid
                high_sex = mid_sex
            else:
                low = mid
                low_sex = mid_sex


if __name__ == '__main__':
    solve(int(input()))

Solution (Python):
n = int(input())

li = 0
print(li)
ls = input()
if ls=="Vacant":
    exit()

ri = n-1
print(ri)
rs = input()
if rs=="Vacant":
    exit()

while ri>li:
    mid = (ri+li)//2
    print(mid)
    s = input()

    if s=="Vacant":
        exit()
    
    if (mid-li)%2==0:
        if s!=ls:
            ri = mid
            rs = s
        else:
            li = mid
            ls = s
    else:
        if s!=ls:
            li = mid
            ls = s
        else:
            ri = mid
            rs = s

Solution (Python):
n=int(input())
n0=0
print(n0)
s=input()
if s=='Vacant':
    exit()
sl=s    
l,r=0,n 
m=(l+r)//2 
print(m)
sm=input()
while sm!='Vacant' and l<r:
    if sm==sl and (m-l)%2==0:
        l=m
        sl=sm
    elif sm!=sl and (m-l)%2==1:
        l=m
        sl=sm
    else:
        r=m
    m=(l+r)//2
    print(m)
    sm=input()
if l>=r:
    print(l,r)

Solution (Python):
n = int(input())

print(0)
lf = input()
if lf == "Vacant":
    exit()

print(n-1)
rf = input()
if rf == "Vacant":
    exit()
l = 0
r = n-1

while True:
    k = (l+r)//2
    print(k)
    f = input()
    if f == "Vacant":
        exit()
    else:
        if (abs(r-k) % 2 == 1 and rf == f) or (abs(r-k) % 2 == 0 and rf != f):
            l = k
            lf = f
        elif (abs(l-k) % 2 == 1 and lf == f) or (abs(l-k) % 2 == 0 and lf != f):
            r = k
            rf = f

Solution (Python):
N=int(input())
l,r=0,N
now=-1
print(0)
a=input()
li=['Male','Famale']
if(a=='Vacant'):
    print(0)
    exit()
elif(a=='Male'):
    now=0
else:
    now=1
for _ in range(19):
    Q=((l+r)//2)%N
    print(Q)
    ans=input()
    if(ans=='Vacant'):
        print(Q%N)
        exit()
    res=-1
    if(ans=='Male'):
        res=0
    else:
        res=1
    if((Q-l-1)%2==1 and res!=now) or ((Q-l-1)%2==0 and res==now):
        r=Q
    else:
        l=Q
        now=res
print((l+r)//2%N)

Solution (Python):
N = int(input())
print(0,flush=True)
zero = input()
if zero == 'Vacant':
    exit()
l = 0
r = N-1
while True:
    if r-l <= 1:
        print(r,flush=True)
        if input() == 'Vacant':
            exit()
        print(l,flush=True)
        if input() == 'Vacant':
            exit()
    k = (r+l)//2
    print(k,flush=True)
    seat = input()
    if seat == 'Vacant':
        exit()
    else:
        if k%2:
            if seat == zero:
                r = k
            else:
                l = k
        else:
            if seat == zero:
                l = k
            else:
                r = k

Solution (Python):
n = int(input())

lst = [-1 for i in range(n)]
print(0)
sex0 = input()
if sex0 == 'Male':
    lst[0] = 1
    leftsex = 1
elif sex0 == 'Female':
    lst[0] = 0
    leftsex = 0
else:
    exit()

print(n-1)
sexn_1 = input()
if sexn_1 == 'Male':
    lst[n-1] = 1
    rightsex = 1
elif sexn_1 == 'Female':
    lst[n-1] = 0
    rightsex = 0
else:
    exit()

left = 0
right = n-1
while left+1 < right:
    mid = (left+right)//2
    print(mid)
    sexmid = input()
    if sexmid == 'Male':
        lst[mid] = 1
        midsex = 1
    elif sexmid == 'Female':
        lst[mid] = 0
        midsex = 0
    else:
        exit()
    
    if (mid-left) % 2 == abs(midsex-leftsex):
        left = mid
        leftsex = midsex
    else:
        right = mid
        rightsex = midsex

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())

    
    print(0)
    left_response = input()
    if left_response == "Vacant":
        exit()

    print(n - 1)
    right_response = input()
    if right_response == "Vacant":
        exit()

    left = 0
    right = n - 1

    for i in range(20):
        mid = (left + right) // 2
        print(mid)
        mid_response = input()

        if mid_response == "Vacant":
            exit()

        if (mid - left) % 2 == 0 and left_response == mid_response:
            left = mid
            left_response = mid_response
        elif (mid - left) % 2 == 1 and left_response != mid_response:
            left = mid
            left_response = mid_response
        else:
            right = mid
            right_response = mid_response


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())

print(0)
s = input()
m = s[0]
if m=="V":
    exit()
else:
    b = m
print(n-1)
s = input()
m = s[0]
if m=="V":
    exit()

for i in range(20):
    if i==0:
        r = 0
        l = n - 1
        q = (r+l)//2
    else:
        q = (r+l)//2
    print(q)
    s = input()
    m = s[0]
    if m=="V":
        exit()
    else:
        if m==b and (q-r+1)%2==1:
            r = q
        elif m==b and (q-r+1)%2==0:
            l = q
        elif m!=b and (q-r+1)%2==1:
            l = q
        elif m!=b and (q-r+1)%2==0:
            r = q
            b = m
        else:
            print("E")
print("End")

Solution (Python):
gender = {"Male":0,"Female":1}

N = int(input())

print(0)
left_str = input()
if left_str == "Vacant":
    exit()
print(N-1)
right_str = input()
if right_str == "Vacant":
    exit()

left = 0
right = N-1

for i in range(20):
    mid = (left+right)//2

    print(mid)
    mid_s = input()

    if mid_s == "Vacant":
        exit()

    if gender[mid_s] == (gender[left_str]+mid)%2:
        left = mid
    else:
        right = mid

Solution (Python):
import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0

print(left, flush=True)
l = input()
if l == "Vacant":
    exit()
    
print(right, flush=True)
r = input()
if r == "Vacant":
    exit()

while left + 1 != right:
    mid = (right + left) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()
        
    if ((mid - left) % 2 == 0 and l != m) or ((mid - left) % 2 == 1 and l == m):
        right = mid
        r = m
    else:
        left = mid
        l = m

Solution (Python):
def main():
    import sys
    N = int(input())
    A = ["?"]*N
    pos = N//2
    left = 0
    right = N
    if A[left] == "?":
        print(left)
        sys.stdout.flush()
        S = input()[0]
        if S == "V":
            return
        A[left] = S
    if A[right-1] == "?":
        print(right-1)
        sys.stdout.flush()
        S = input()[0]
        if S == "V":
            return
        A[right-1] = S
    for i in range(20):
        pos = (left+right)//2
        if A[pos] == "?":
            print(pos)
            sys.stdout.flush()
            S = input()[0]
            if S == "V":
                return
            A[pos] = S

        if (pos - left) % 2 == 0:
            if A[pos] == A[left]:
                left = pos
            else:
                right = pos
        else:
            if A[pos] != A[left]:
                left = pos
            else:
                right = pos


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    N = int(input())
    A = ["?"]*N
    pos = N//2
    left = 0
    right = N
    if A[left] == "?":
        print(left)
        sys.stdout.flush()
        S = input()[0]
        if S == "V":
            return
        A[left] = S
    for i in range(20):
        pos = (left+right)//2
        if A[pos] == "?":
            print(pos)
            sys.stdout.flush()
            S = input()[0]
            if S == "V":
                return
            A[pos] = S

        if (pos - left) % 2 == 0:
            if A[pos] == A[left]:
                left = pos
            else:
                right = pos
        else:
            if A[pos] != A[left]:
                left = pos
            else:
                right = pos


if __name__ == '__main__':
    main()

Solution (Python):
import sys
n=int(input())

print(0)
sexlow=input()
if(sexlow=='Vacant'):
    sys.exit()

print(n-1)
sexhigh=input()
if(sexhigh=='Vacant'):
    sys.exit()

low=0
high=n-1
piv=0
while(True):
    piv=(low+high)//2

    print(piv)
    sexn=input()
    if(sexn=='Vacant'):
        break
    elif(( (piv-low)%2==0 and sexlow!=sexn) or ( (piv-low)%2!=0 and sexlow==sexn)):
        high=piv
        sexhigh=sexn
    elif(( (high-piv)%2==0 and sexhigh!=sexn) or ( (high-piv)%2!=0 and sexhigh==sexn)):
        low=piv
        sexlow=sexn

Solution (Python):
def main():
    import sys
    N = int(input())
    A = ["?"]*N
    pos = N//2
    left = 0
    right = N
    for i in range(20):
        pos = (left+right)//2
        if A[pos] == "?":
            print(pos)
            sys.stdout.flush()
            S = input()[0]
            if S == "V":
                return
            A[pos] = S
        if A[left] == "?":
            print(left)
            sys.stdout.flush()
            S = input()[0]
            if S == "V":
                return
            A[left] = S

        if (pos - left) % 2 == 0:
            if A[pos] == A[left]:
                left = pos
            else:
                right = pos
        else:
            if A[pos] != A[left]:
                left = pos
            else:
                right = pos


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())

print(0)
s = str(input())
if s == 'Vacant':
    exit()
s0 = s

print(n-1)
s = str(input())
if s == 'Vacant':
    exit()

def is_ok(x):
    print(x)
    s = str(input())
    if s == 'Vacant':
        exit()
    if x%2 == 1:
        if s != s0:
            return False
        else:
            return True
    else:
        if s == s0:
            return False
        else:
            return True


l = 0
r = n-1
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c

Solution (Python):
import sys




def judge(x):
    print(x)
    sys.stdout.flush()
    s = input()
    
    
    if s=='Vacant':
        print(x)
        exit()
        
    if x%2==0 and s!=ini_s:
        return True
    elif x%2==1 and s==ini_s:
        return True
    else:
        return False

N = int(input())
print(0)
sys.stdout.flush()
ini_s = input()


if ini_s=='Vacant':
    print(0)
    exit()

print(N-1)
sys.stdout.flush()
last_s = input()


if last_s=='Vacant':
    print(N-1)
    exit()

l, r = 1, N-1
    
while l<=r:
    m = (l+r)//2
        
    if judge(m):
        r = m-1
    else:
        l = m+1

print(l-1)
exit()

Solution (Python):
n = int(input())
print(0)
s = input()
if s == "Vacant":
    exit()
elif s == "Male":
    print(n-1)
    s = input()
    if s == "Vacant":
        exit()
    else:
        l = 0
        r = n-1
        while True:
            m = (l+r)//2
            print(m)
            s = input()
            if s == "Vacant":
                exit()
            if m % 2 == 0 and s == "Male":
                l = m
            elif m % 2 == 1 and s == "Female":
                l = m
            else:
                r = m
elif s == "Female":
    print(n-1)
    s = input()
    if s == "Vacant":
        exit()
    else:
        l = 0
        r = n-1
        while True:
            m = (l+r)//2
            print(m)
            s = input()
            if s == "Vacant":
                exit()
            if m % 2 == 0 and s == "Male":
                r = m
            elif m % 2 == 1 and s == "Female":
                r = m
            else:
                l = m

Solution (Python):
def printt(x):
  print(x,flush=True)
  i=input()
  if i=="Vacant":exit()
  if i=="Male":return 0
  return 1
n=int(input())
ng=0
ok=n
f=printt(0)
while ng+1!=ok:
  mid=(ok+ng)//2
  if printt(mid)==(f+mid)%2:ng=mid
  else:ok=mid

Solution (Python):




N = int(input())


def query(idx):
    print(idx)
    s = input()
    if s == "Vacant":
        exit()
    
    return s

base = query(0)

def is_ok(mid):
    s = query(mid)
    
    if mid % 2 == 0:
        return s == base
    
    else:
        return s != base

lo = 0
hi = N
while hi - lo > 1:
    mid = (hi + lo) // 2
    if is_ok(mid):
        lo = mid
    else:
        hi = mid

Solution (Python):

N = int(input())

print(0, flush=True)
S = input()
if S == "Vacant":
    exit()
lo = 0
hi = N
while hi - lo > 1:
    mid = (hi + lo) // 2
    print(mid, flush=True)
    tmp = input()
    if tmp == "Vacant":
        exit()
    else:
        if mid % 2 == 0:
            if tmp == S:
                lo = mid
            else:
                hi = mid
        else:
            if tmp != S:
                lo = mid
            else:
                hi = mid

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

l = 0
r = N
print(0, flush=True)
retl = input()
if retl == "Vacant": exit()
print(N-1, flush=True)
retr = input()
if retr == "Vacant": exit()
while l+1 != r:
	m = (l+r)//2
	print(m, flush=True)
	retm = input()
	if retm == "Vacant": exit()
	if (l-m)%2 == 0 and retl == retm or (l-m)%2 == 1 and retl != retm:
		l = m
		retl = retm
	else:
		r = m
		retr = retm

print(l, flush=True)
_ = input()

Solution (Python):
import sys

N = int(input())

S = [''] * N


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        print(i)
        sys.exit()
    S[i] = s
    return s


query(0)
query(N - 1)
l = 0
r = N - 1
while r - l >= 2:
    m = (l + r) // 2
    if r - l == 2 and S[l] != S[r]:
        break
    query(m)
    if (m - l) % 2 == 0 and S[l] != S[m] or (m - l) % 2 == 1 and S[l] == S[m]:
        r = m
    else:
        l = m

for i in range(l, r + 1):
    if S[i] == '':
        print(i)
        break

Solution (Python):


def main():
    n = int(input())

    print(0,flush=True)
    s = input()
    if s=="Vacant": return 0
    cap = 0
    if s=="Female": cap = 1

    lo = 0
    hi = n
    while True:
        mid = (hi+lo)//2
        print(mid, flush=True)
        s = input()

        if s=="Vacant": return 0
        gen = 0
        if s=="Female": gen = 1

        if (cap+mid)%2 == gen:
            lo = mid
        else:
            hi = mid

main()

Solution (Python):
n = int(input())
import sys

def ato(x):
    if x == "Male":
        return 0
    elif x == "Female":
        return 1
    else:
        return -1
    
print(0)
s0 = ato(input())
if s0 == -1:
    sys.exit()
    
print(n-1)
s1 = ato(input())
if s1 == -1:
    sys.exit()
    
left = 0
right = n-1
center = (left+right) // 2
while True:
    center = (left+right) // 2
    
    print(center)
    s2 = ato(input())
    if s2 == -1:
        break
    
    if (center - left)%2 == abs(s2 - s0):
        left = center
        s0 = s2
    else:
        right = center
        s1 = s2