30231번 - The Duel of Smokin’ Joe 다국어

문제

In the wild west, they take their Computer Science very seriously. Smokin’ Joe is widely known for his skills, and outlaws come from across the land to challenge him in a good ol’ fashioned sortin’ duel. The way that outlaws duel in the wild west, of course, is trying to be the one who makes the last move to sort an array of integers.

One fateful day, Smokin’ Joe’s nemesis, an infamous character known as The Outlaw, came to town and challenged Joe to a duel. The rules of the duel are as follows: the outlaw will spin the chambers, and a random permutation of length n will fall out (a permutation of length n is an array of the integers from 1 to n in any order). Smokin’ Joe and The Outlaw will take turns swapping two elements in this permutation, until the permutation is sorted in increasing order. The winner is the player who makes the last swap. Once an element is in its final position (i.e., value k is at position k), that element cannot be moved for the rest of the game; otherwise, there are no restrictions on which two elements can be swapped.

Both Smokin’ Joe and The Outlaw will always play perfectly, i.e., they play to win and not necessarily to sort the list as quickly as possible. Can you predict who will win?

Given a permutation, predict the winner of the game, where players take turns swapping elements, and an element cannot move once it’s in its final sorted position. The winner is the person who makes the final move to sort the array. Note that Smokin’ Joe goes first, i.e., makes the first move.

입력

The input will consist of two lines. The first input line contains an integer, n (1 ≤ n ≤ 10⁶), the length of the permutation. The second input line contains n distinct integers, the permutation. It is guaranteed that it will be a permutation of the integers from 1 to n, and the permutation is not already sorted.

출력

If Smokin’ Joe wins, print “Smokin Joe!” (note that the apostrophe of Smokin’ is omitted in the output since apostrophe may come out as different ASCII characters on different machines and may cause “format errors” in the output). If The Outlaw wins, print “Oh No!”.

제한

힌트