Range Game
Limits: 2 sec., 256 MiB
Zenyk and Marichka have \(N\) stones placed in a row. The \(i\)-th stone has number \(A_i\) written on it.
Zenyk and Marichka are playing game. They take turns alternately. Marichka moves first. On each turn player takes some non-empty continuous range of stones. For example, we have a row with stones \([4,7,2,5,9]\). Player can choose to take stones with numbers \(2\) and \(5\). After the turn the new row will look like this: \([4,7,9]\). The game ends when all stones are taken.
When player took stone with number \(x\), he receives \(N^x\) penalty points. Player who has less penalty points is the winner of the game.
Determine, who will win this game if both players are playing optimally.
Input
The first line contains one integer \(N\). The second line contains \(N\) integers \(A_i\).
Output
Print Zenyk
, if Zenyk will win, Marichka
if
Marichka will win and Draw
if the game ends up with
draw.
Constraints
\(1 \le N \le 10^5\),
\(0 \le A_i \le 10^9\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4 4 4 7 1 | Marichka |
Input (stdin) | Output (stdout) |
---|---|
2 7 7 | Draw |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|