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