import Control.Applicative
import Control.Monad
import Data.IORef
import qualified Data.Vector as V

main :: IO ()
main = do
    n <- readLn
    table <- V.fromList <$> replicateM n (newIORef "Unknown")
    print 0
    head <- getLine
    print (n-1)
    end <- getLine
    writeIORef (table V.! 0) head
    writeIORef (table V.! (n-1)) end
    res <- loop table 0 (n - 1)
    return ()

loop :: V.Vector (IORef String) -> Int -> Int -> IO Int
loop table a b = do
    let mid = if even (a + b) then (a+b) `div` 2 else (a+b-1) `div` 2
    print mid
    seat <- getLine
    writeIORef (table V.! mid) seat
    case seat of
        "Vacant" -> return mid
        _ -> do
            frontValid <- isValid table a mid
            rearValid <- isValid table mid b
            if not frontValid then
                loop table a mid
            else if not rearValid then
                loop table mid b
            else returnVacant table a b

returnVacant :: V.Vector (IORef String) -> Int -> Int -> IO Int
returnVacant table p q = do
    pContent <- readIORef (table V.! p)
    qContent <- readIORef (table V.! q)
    if pContent == "Vacant" then
        return p
    else if qContent == "Vacant" then
        return q
    else do
        print "ERROR"
        return 12345

-- Is range valid
isValid :: V.Vector (IORef String) -> Int -> Int -> IO Bool
isValid table p q = do
    pContent <- readIORef (table V.! p)
    qContent <- readIORef (table V.! q)
    let diff = q - p
    if pContent == "Vacant" || qContent == "Vacant" then
        return False
    else if even diff && pContent == qContent then
        return True
    else if odd diff && pContent /= qContent then
        return True
    else
        return False
    
