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,
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 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 the word "Cheater" if Chichikov could not pocket all
the N balls in the right order, otherwise output
"Not a proof".
Not a proof
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