ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1494. Monobilliards

Time limit: 1.0 second
Memory limit: 64 MB
A monobilliards table set up in a gaming house of a town N turned out to be a very profitable investment, but only till the day the famous Mr. Chichikov came to the town. Chichikov was winning again and again, and the owner was counting his losses suspecting that something was wrong. But he couldn't prove the cheating until an inspector from Petersburg arrived in the town.
The rules of monobilliards are very simple. One has to pocket successively the balls with numbers 1, 2, …, N into the only pocket (exactly in this order). While Mr. Chichikov was playing, the inspector several times came up to the table and took out from the table's pocket the last of the pocketed balls. In the end it turned out that Chichikov had pocketed all the balls and the inspector had taken out and inspected them. The cheater claimed that he had pocketed the balls in the right order! The owner understood that this was his chance, because the inspector had to remember the order in which he had taken out the balls. But would it be so easy to prove the cheating?

Input

The first line contains the number of billiard balls N (1 ≤ N ≤ 100000). In the next N lines there are the numbers of the balls in the order in which the inspector took them out from the pocket.

Output

Output the word "Cheater" if Chichikov could not pocket all the N balls in the right order, otherwise output "Not a proof".

Samples

inputoutput
2
2
1
Not a proof

3
3
1
2
Cheater

Notes

In the first sample, Chichikov could pocket the balls in the right order if the inspector took them out after Chichikov pocketed the second ball. In the second sample, Chichikov could pocket the balls in any order excepting the right one 1-2-3.
Problem Author: Alex Samsonov
Problem Source: XIII-th USU Junior Contest, October 2006