Rabbit Stewie enjoys arrays for ages. Once his friend Megan decided to tease Stewie... Meg entered the room at the precise moment when he almost had proven the theory of correlation between cosmic microwave background radiation and ordered array of letters found in dinner soup. She began badgering on Stewie, saying that he should know everything about arrays, but still can't beat her in that famous "Array game". Stewie tried to stay calm, but it did not last long. Eventually they decided to find out who is right by the competition.

A permutation of n first natural numbers is given. One can remove a single number from the permutation in a turn. Two players do the removals one by one; Stewie starts. The winner is determined when there are two numbers left. In case the left number is less than the number on right – Stewie wins, otherwise – Meg wins. The game is a fun, but Stewie does not want to waste his time on it. Both rabbits completed trainings on optimal "Array games" so they both play optimally. We need you to help speeding up the process, and determine the winner before the game starts.

Input

The first line contains the only number n (2 ≤ n ≤ 4000), the second line contains n integers that form a permutations of numbers 1, 2, 3, ..., n.

Output

Print Stewie or Meg - the winner of the game in case both playing optimally.