eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Массивные игры

Массивные игры

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Крилик Стьюи увлекается массивами уже не первый год. Однажды от нечего делать крилик Меган очень сильно заскучала и решила потроллить Стьюи... Как раз в этот момент, когда он уже почти доказал теорию о связи реликтового излучения и отсортированного массива из букв, найденных в обеденном супе, Мег вошла в комнату и начала издеваться над Стьюи, мол, он должен знать о массивах всё, но всё-равно не сможет обыграть её в столь знаменитой "Массивной игре".

Стьюи старался не троллится, но это длилось не долго. В конце концов они решили выяснить, кто же из нх прав при помощи соревнования... Итак, дана перестановка n первых натуральных чисел. За один ход можно удалить из перестановки только одно число. Ходят по очереди, начинает Стьюи. Победитель определяется тогда, когда на столе останется только два числа: если число слева окажется меньше числа справа - выиграл Стьюи, иначе - Мег. Все было бы хорошо, да только не желает крилик Стьюи тратить время на такую бестолковую игру. Оба крилика в прошлом году прошли курсы оптимальной игры в "Массивные игры", и поэтому оба играют оптимально. Помогите ускорить процесс, определив победителя ещё до начала игры.

Входные данные

В первой строке находится одно целое число n (2n4000). Во второй строке заданы n целых чисел, образующих перестановку чисел 1, 2, 3, ..., n.

Выходные данные

Выведите Stewie или Meg в зависимости от того, кто выиграет при оптимальной игре обоих.

Пример

Входные данные #1
3
2 3 1
Выходные данные #1
Stewie
Входные данные #2
4
4 2 3 1
Выходные данные #2
Meg
Источник ACM-ICPC Ukraine 2012, 1st Stage Ukraine, April 21, 2012