#include<iostream>
using namespace std;
int array[100000];
int main()
{
    long n;
    long number,lastnumber=0;
    cin>>n;
    long flag=0;
    for(int j=0;j<100000;j++)
        array[j]==0;
    for(long i=0;i<n;i++)
    {
        cin>>number;
        if(array[number-1]==1)
        { cout<<"Cheater"; return 0; }
        array[number-1]=1;
        if(lastnumber)
            if(!flag) {
                if(number<=lastnumber)
                    flag=1; }
            else if(flag)
                if(number>=lastnumber)
                { cout<<"Cheater"; return 0; }
        lastnumber=number;

    }
    cout<<"Not a proof";
    return 0;
}

Test it with these data:
6
3
4
2
1
5
6
Answer is "Not a proof"
P.S. Please DO NOT put your code, you can explain your algo.