Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


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


def is_ok(ind):
    global ng
    global leftans
    # 左ならTrue
    response = query(ind)
    if (ind-ng) % 2 == 1:
        return leftans == response
    else:
        leftans = response
        return leftans != response


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

    # 適当にいじる
    ng = 0  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


leftans = query(0)
bin_search_meguru()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


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

# 適当にいじる
ng = -1  # ind=0が条件を満たすこともあるため
ok = N  # ind=len(a)-1が条件を満たさないこともあるため

# いじらない
# okとngのどちらが大きいかわからないことを考慮
while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid




Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


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

# 適当にいじる
ng = -1  # ind=0が条件を満たすこともあるため
ok = N  # ind=len(a)-1が条件を満たさないこともあるため

# いじらない
# okとngのどちらが大きいかわからないことを考慮
while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
return False




Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

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

root=query(0)

def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False

bin_search_meguru()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

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

root=query(0)

def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False

bin_search_meguru()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())

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

root=query(0)

def is_ok(ind):
    """
    indが条件を満たすかどうか．問題ごとに定義
    ex.
    if a[ind] >= key:
        return True
    else:
        return False
    """
    # 左ならTrue
    response=query(ind)
    if ind%2==1 and root==response:
        return True
    else: return False



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

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False

bin_search_meguru()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
print(0)
s = str(input())
if s=='Vacant':
    exit()
temp = s

def is_ok():
    if temp == s and abs(mid-ng) % 2 == 1:
        return True
    elif temp != s and abs(mid-ok) % 2 == 0:
        return False


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

    # 適当にいじる
    ng = 0  
    ok = N-1  # ind=len(a)-1が条件を満たさないこともあるため
    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        print(mid)
        s = str(input())
        if is_ok():
            ok = mid
            temp=s
        else:
            ng = mid
            temp=s

bin_search_meguru()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
# https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9
print(0,flush=True)
s=str(input())
temp=s
tempway='right'
templind=0

l=0
def is_ok():
    if temp==s and (mid-templind)%2==1:
        if tempway=='right':
            return True
        else: return False
    elif temp!=s and (mid-tmeplind)%2==0:
        if tempway=='right':
            return False
        else: return True
    else:
        exit()


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

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため
    tempway='left'
    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        print(mid,flush=True)
        s=str(input())
        if is_ok():
            ok = mid
            tempway='left'
        else:
            ng = mid
            templind=mid
            tempway='right'
bin_search_meguru()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
# https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9
print(0,flush=True)
s=str(input())
temp=s
tempway='right'
templind=0

l=0
def is_ok():
    if temp==s and (mid-templind)%2==1:
        if tempway=='right':
            return True
        else: return False
    elif temp!=s and (mid-tmeplind)%2==0:
        if tempway=='right':
            return False
        else: return True
    else:
        exit()


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

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため
    tempway='left'
    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        print(mid,flush=True)
        s=str(input())
        if is_ok():
            ok = mid
            tempway='left'
        else:
            ng = mid
            templind=mid
            tempway='right'
bin_search_meguru()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
# https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9
print(0,flush=True)
s=str(input())
temp=s
tempway='right'
l=0
def is_ok():
    if temp==s and (mid-l)%2==1:
        if tempway=='right':
            return True
        else: return False
    elif temp!=s and (mid-l)%2==0:
        if tempway=='right':
            return False
        else: return True
    else:
        exit()


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

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        print(mid,flush=True)
        s=str(input())
        if is_ok():
            ok = mid
            tempway='left'
        else:
            ng = mid
            l=mid
            tempway='right'
bin_search_meguru()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        plsex = 0
    else:
        plsex = 1

    pl = 0
    pr = N
    while pl + 1 < pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        else:
            if s == 'Male':
                pcsex = 0
            else:
                pcsex = 1
        if (pc - pl) % 2 == 1 and plsex == pcsex:
            pr = pc
        else:
            plsex = pcsex
            pl = pc


resolve()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i,flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s=='Male':
        plsex=0
    else: plsex=1

    pl = 0
    pr = N
    while pl + 1 < pr:
        pc = (pl + pr) // 2
        print(pc,flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            pcsex=0
            if (pc - pl) % 2 == 1 and plsex==pcsex:
                pr = pc
            else:
                plsex = pcsex
                pl = pc
        else:
            pcsex=1
            if (pc - pl) % 2 == 1 and plsex == pcsex:
                pr = pc
            else:
                plsex = pcsex
                pl = pc


resolve()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i,flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        plsex = s

    pl = 0
    pr = N
    while True:
        pc = (pl + pr) // 2
        print(pc,flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pc - pl) % 2 == 1 and plsex == s:
                pr = pc
            else:
                plsex = s
                pl = pc
        else:
            if (pc - pl) % 2 == 1 and plsex == s:
                pr = pc
            else:
                plsex = s
                pl = pc


resolve()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        plsex = s

    pl=0
    pr=N
    while pl + 1 < pr:
        pc = (pl + pr) // 2
        print(pc)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pc - pl) % 2 == 1 and plsex == s:
                pr = pc
            else:
                plsex = s
                pl = pc
        else:
            if (pc - pl) % 2 == 1 and plsex == s:
                pr = pc
            else:
                plsex = s
                pl = pc



resolve()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        temp = s

    pl=0
    pr=N
    while pl + 1 < pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pc - pl) % 2 == 1 and temp == s:
                pr = pc
            else:
                temp = s
                pl = pc
        else:
            if (pc - pl) % 2 == 1 and temp == s:
                temp = s
                pr = pc
            else:
                temp = s
                pl = pc



resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        temp = s

    pl=0
    pr=N
    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pc - pl) % 2 == 1 and temp == s:
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1
        else:
            if (pc - pl) % 2 == 1 and temp == s:
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1


resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        temp = s

    pl=0
    pr=N
    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pc - pl) % 2 == 1 and temp != 'Male':
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1
        else:
            if (pc - pl) % 2 == 1 and temp != 'Female':
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1


resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        temp = s

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        if i % 2 == 1 and temp != 'Male':
            temp = s
            pl, pr = 0, N // 2
        else:
            temp = s
            pl, pr = N // 2, N
    else:
        if i % 2 == 1 and temp != 'Female':
            temp = s
            pl, pr = 0, N // 2
        else:
            temp = s
            pl, pr = N // 2, N

    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pr - pl) % 2 == 1 and temp != 'Male':
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1
        else:
            if (pr - pl) % 2 == 1 and temp != 'Female':
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1


resolve()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
# import bisect
# from collections import Counter, deque # https://note.nkmk.me/python-scipy-connected-components/
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


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

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    else:
        temp = s

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        if i % 2 == 1 and temp != 'Male':
            temp = s
            pl, pr = 0, N // 2
        else:
            temp = s
            pl, pr = N // 2 + 1, N
    else:
        if i % 2 == 1 and temp != 'Female':
            temp = s
            pl, pr = 0, N // 2
        else:
            temp = s
            pl, pr = N // 2 + 1, N

    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pr - pl) % 2 == 1 and temp != 'Male':
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1
        else:
            if (pr - pl) % 2 == 1 and temp != 'Female':
                temp = s
                pr = pc - 1
            else:
                temp = s
                pl = pc + 1


resolve()


Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        temp = 1
    else:
        temp = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        if i % 2 == 1 and temp != 1:
            temp = 1
            pl, pr = 0, N // 2
        else:
            temp = 1
            pl, pr = N // 2 + 1, N
    else:
        if i % 2 == 1 and temp != 2:
            temp = 2
            pl, pr = 0, N // 2
        else:
            temp = 2
            pl, pr = N // 2 + 1, N

    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pr - pl) % 2 == 1 and temp != 1:
                temp = 1
                pr = pc - 1
            else:
                temp = 1
                pl = pc + 1
        else:
            if (pr - pl) % 2 == 1 and temp != 2:
                temp = 2
                pr = pc - 1
            else:
                temp = 2
                pl = pc + 1


resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        temp = 1
    else:
        temp = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        if i % 2 == 1 and temp != 1:
            temp = 1
            pl,pr=0,N//2
        else:
            temp = 1
            pl,pr=N//2+1,N-1
    else:
        if i % 2 == 1 and temp != 2:
            temp = 2
            pl,pr=0,N//2
        else:
            temp = 2
            pl,pr=N//2+1,N-1

    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pr - pl) % 2 == 1 and temp != 1:
                temp = 1
                pr = pc - 1
            else:
                temp = 1
                pl = pc + 1
        else:
            if (pr - pl) % 2 == 1 and temp != 2:
                temp = 2
                pr = pc - 1
            else:
                temp = 2
                pl = pc + 1


resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        temp = 1
    else:
        temp = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        if i % 2 == 1 and temp != 1:
            temp = 1
            pl,pr=0,N//2
        else:
            temp = 1
            pl,pr=N//2+1,N-1
    else:
        if i % 2 == 1 and temp != 2:
            temp = 2
            pl,pr=0,N//2
        else:
            temp = 2
            pl,pr=N//2+1,N-1

    while pl <= pr:
        pc = (pl + pr) // 2
        print(pc, flush=True)

        s = str(input())
        if s == 'Vacant':
            sys.exit()
        elif s == 'Male':
            if (pr - pl) % 2 == 1 and temp != 1:
                temp = 1
                pr = pc - 1
            else:
                temp = 1
                pl = pc + 1
        else:
            if (pr - pl) % 2 == 1 and temp != 2:
                temp = 2
                pr = pc - 1
            else:
                temp = 2
                pl = pc + 1


resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())
    L = [-1] * N

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        sys.exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    # リストAをとってkeyのある添字を返す
    # なかったら-1
    def bin_search(pl, pr):

        while pl <= pr:
            pc = (pl + pr) // 2
            print(pc, flush=True)

            s = str(input())
            if s == 'Vacant':
                sys.exit()
            elif s == 'Male':
                L[pc] = 1
            else:
                L[pc] = 2

            if abs(L[pr] - L[pc]) == 0 and (pr - pc) % 2 == 1:
                pr = pc - 1
            else:
                pl = pc + 1

    if abs(L[N // 2] - L[0]) == 0 and (N // 2 % 2 == 1):
        bin_search(0, N // 2)
    else:
        bin_search(N // 2 + 1, N - 1)


resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())
    L = [-1] * N

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        print(i, flush=True)
        exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        print(i, flush=True)
        sys.exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    # リストAをとってkeyのある添字を返す
    # なかったら-1
    def bin_search(pl, pr):

        while pl <= pr:
            pc = (pl + pr) // 2
            print(pc, flush=True)

            s = str(input())
            if s == 'Vacant':
                print(pc, flush=True)
                sys.exit()
            elif s == 'Male':
                L[pc] = 1
            else:
                L[pc] = 2

            if abs(L[pr] - L[pc]) == 0 and (pr - pc) % 2 == 1:
                pr = pc - 1
            else:
                pl = pc + 1

    if abs(L[N // 2] - L[0]) == 0 and (N // 2 % 2 == 1):
        bin_search(0, N // 2)
    else:
        bin_search(N // 2 + 1, N - 1)


resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # emp:0 male:1 female:2
    N = int(input())
    L = [-1] * N

    i = 0
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        print(i, flush=True)
        exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    i = N // 2
    print(i, flush=True)
    s = str(input())
    if s == 'Vacant':
        print(i, flush=True)
        exit()
    elif s == 'Male':
        L[i] = 1
    else:
        L[i] = 2

    # リストAをとってkeyのある添字を返す
    # なかったら-1
    def bin_search(pl,pr):

        while pl <= pr:
            pc = (pl + pr) // 2
            print(pc, flush=True)

            s = str(input())
            if s == 'Vacant':
                print(pc, flush=True)
                exit()
            elif s == 'Male':
                L[pc] = 1
            else:
                L[pc] = 2

            if abs(L[pr] - L[pc]) == 0 and (pr-pc)%2==1:
                pr = pc - 1
            else:
                pl = pc + 1

    if abs(L[N // 2] - L[0]) == 0 and (N//2%2==1):
        bin_search(0,N//2)
    else:
        bin_search(N//2+1, N-1)





resolve()

Fixed submission:
N = int(input())


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


root = query(0)


def is_ok(ind):
    # 左ならTrue
    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  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()