Christmas Wheat

Time limit1sMemory limit32 MB

Summary

Mirko raises one shortest stalk to the next height and Slavko lowers one tallest stalk until two distinct heights remain; report the winner and both extremes.

Level: Medium6 of 10
Topics: Sorting, Prefix sum, Greedy, Game theory
Solved: No attempts yet

Problem

Mirko and Slavko plant Christmas wheat every year on Saint Lucy's Day. Stalks of wheat grow at different speeds, so after a while the field becomes quite messy. They decided to fix that by playing the following game.

On Mirko's turn he picks one stalk of minimal height and stretches it until it is as tall as the shortest stalk that is taller than it.
On Slavko's turn he picks one stalk of maximal height and cuts it until it is as tall as the tallest stalk that is shorter than it.
The game goes on while at least three different heights are left, and the player who cannot move on his turn loses.

Mirko starts. Given the heights of all stalks, determine the winner and the height of the shortest and the tallest stalk at the moment the game ends.

Input

The first line contains the number of wheat stalks $N$ ( $1 \le N \le 10^5$ ).

The second line contains $N$ space separated integers, the heights of the individual stalks. Every height is a positive integer not greater than $10^5$ .

Output

On the first line print Mirko if Mirko wins the game, or Slavko if Slavko wins.

On the second line print the height of the shortest stalk and the height of the tallest stalk at the moment the game ends, separated by a space.

Hint

In the first example every stalk has the same height, so fewer than three different heights are left and Mirko cannot make the opening move. Slavko wins.

Examples3

Example 1
Input
```
3
3 3 3
```
Expected output
```
Slavko
3 3
```
Example 2
Input
```
4
3 1 2 1
```
Expected output
```
Slavko
1 2
```
Example 3
Input
```
7
2 1 3 3 5 4 1
```
Expected output
```
Slavko
2 3
```