Array games#3204
Rabbit Stewie has enjoyed arrays for years. One day, his friend Megan decided to tease him. Just as Stewie was about to prove the theory of the correlation between cosmic microwave background radiation and an ordered array of letters found in dinner soup, Meg entered the room and began teasing Stewie that although he knows everything about arrays, he still can't beat her in the famous "Array game."
Stewie tried not to get upset, but it didn't last long. Eventually, they decided to settle the matter with a competition.
A permutation of the first natural numbers is given. On each turn, a player may remove exactly one number from the permutation. The players take turns, with Stewie going first. When only two numbers remain, the winner is determined: if the left number is less than the right number, Stewie wins; otherwise, Meg wins. Stewie does not want to waste time on the game. Both rabbits have finished optimal "Array game" courses last year, so they both play optimally. Help speed up the process and determine the winner before the game starts.
The first line contains one integer (2 \le n \le 4000). The second line contains integers, a permutation of the numbers , , , ..., .
Print Stewie or Meg, depending on who will win if both play optimally.
Example 1
Example 2