{-# LANGUAGE BangPatterns #-}

import Data.Bool (bool)

main :: IO ()
main = do
    n  <- read <$> getLine
    xs <- fmap read . words <$> getLine
    answer $ solve n xs

type Answer = Int
answer :: Answer -> IO ()
answer = print

solve :: Int -> [Int] -> Int
solve n = bin 2 (2 * n - 2)
  where
    bin l g
      | l == g    = const g
      | r == 1    = bool l g . gte g
      | otherwise = bool . bin l (m - 1) <*> bin m g <*> gte m
      where
        r = g - l
        m = l + r `div` 2
    gte x = go . foldr ((:) . (x <=)) []
    go (x : y : xs)
      | x == y    = left   2 x y $ zip [3 ..] xs
      | otherwise = left   0 x y $ zip [3 ..] xs
    left !l !w z xs@((i, x) : xs')
      | i >= n    = middle l w z xs
      | z /= x    = left   l w x xs'
      | otherwise = left   i x x xs'
    middle l w z xs@((i, x) : xs')
      | i >  n    = right  m w z xs
      | z /= x    = right  m w x xs'
      | otherwise = x
      where
        m = 2 * n - l
    right m w z [(i, x)]
      | z /= x    = w
      | otherwise = x
    right m w z ((i, x) : xs)
      | i >  m    = w
      | z /= x    = right m w x xs
      | otherwise = x
