Buggy python submission (verdict: Time Limit Exceeded):
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        left = mid
        l_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        left = mid
        l_sex = sex
    else:
        right = mid - 1

print(left, flush=True)
exit(0)


Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

Buggy python submission (verdict: Time Limit Exceeded):
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != sex:
        left = mid + 1
    elif (mid - left) % 2 == 1 and sex == sex:
        left = mid + 1
    else:
        right = mid - 1

print(left, flush=True)
exit(0)


Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

Buggy python submission (verdict: Time Limit Exceeded):
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

axis = val(0)

ng = 0
ok = n - 1

while ng + 1 < ok:
    mid = (ng + ok) // 2
    sex = val(mid)
    if sex == axis:
        ng = mid
    else:
        ok = mid

print(ng, flush=True)
exit(0)


Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

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

print(0, flush=True)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid
    else:
        right = mid

print(left, flush=True)
exit(0)


Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

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

print(0, flush=True)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid
    cnt += 1
    if cnt >= 20:
        exit(0)

print(left, flush=True)
exit(0)


Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

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

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

cnt = 0
while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid
    cnt += 1
    if cnt >= 20:
        exit(0)

print(left)
exit(0)


Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

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

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid

print(left)
exit(0)


Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

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

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid

print(left)
exit(0)



Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

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

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid

print(left)



Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)

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

print(0)
sex = input()
if sex == "Vacant":
    exit(0)
axis = sex

left = 1
right = n

while left + 1 < right:
    mid = (left + right) // 2
    print(mid)
    sex = input()
    if sex == "Vacant":
        exit(0)
    elif sex == axis:
        left = mid + 1
    else:
        right = mid - 1

print(left)



Fixed submission:
def val(num):
    print(num, flush=True)
    sex = input()
    if sex == "Vacant":
        exit(0)
    return 1 if sex == "Male" else 0


n = int(input())

l_sex = val(0)
r_sex = val(n - 1)

left = 0
right = n - 1

while left < right:
    mid = (left + right) // 2
    sex = val(mid)
    if (mid - left) % 2 == 0 and sex != l_sex:
        right = mid
        r_sex = sex
    elif (mid - left) % 2 == 1 and sex == l_sex:
        right = mid
        r_sex = sex
    else:
        left = mid
        l_sex = sex

print(left, flush=True)
exit(0)