Once again Uolevi and Maija are playing a game. They have a pile of blocks which is initially empty. Uolevi has $n$ blocks labeled with integers $1, \ldots, n$. In the game Uolevi puts the blocks on top of the pile in that order and Maija sometimes removes a block from the top of the pile and writes down the number on it. In the end Uolevi has put all of the blocks into the pile and Maija has removed all of them.

Uolevi sometimes cheats in the game and puts the blocks into the pile in an incorrect order. Given the numbers in the order Maija wrote them down, can you detect if Uolevi cheated?

Input

The first line contains the number blocks $n$. The next $n$ contain the numbers of the blocks in the order in which Maija removed them from the pile. Each of the integers $1, \ldots, n$ appears exactly once in the input.

Output

Output Cheater if you can be sure that Uolevi cheated in the game. Otherwise output Not a proof.

Constraints

• $1 \le n \le 10^5$

Examples

Input:

2
2
1

Output:

Not a proof

Input:

3
3
1
2

Output:

Cheater

Input:

4
2
1
4
3

Output:

Not a proof