1494.cpp

#include <iostream>
#include <stack>

/**
 * Попробуем положить шары в стек так же, как их забивал бы Чичиков.
 * Если текуший шар больше, чем максимальный на данный момент, то считаем, что все в порядке, потому что именно в этом
 * порядке шары попадают в лунку. (Если же он больше на несколько позиций, то, возможно, ревизор не подходил за шарами
 * в момент, пока Чичиков забивал шары с номерами между максимальным и текущим, там собрался еще один стак шаров. Чтобы
 * это проверить, сохраним все шары, которые должны были попасть в лунку в этот промежуток)
 * Если текущий шар меньше, то надо проверить, соответствует ли этот шар ожидаемому стеку, который мы сохранили выше.
 * Если не соответствует, то Чичиков жульничает. 
 */

int main() {
    int n;
    std::cin >> n;
    std::stack<int> balls;
    int tmp_max = 0;
    for (int i = 0; i < n; ++i) {
        int cur;
        std::cin >> cur;
        if (cur > tmp_max) {
            for (int j = tmp_max + 1; j <= cur - 1; j++) {
                balls.push(j);
            }
            tmp_max = cur;
        } else {
            if (cur == balls.top()){
                balls.pop();
            } else {
                std::cout << "Cheater";
                return 0;
            }
        }
    }
    std::cout << "Not a proof";
    return 0;
}