T. Хайпанём немножечко!

Блокчейн (blockchain) переводится как «цепочка блоков». Это способ хранения данных, защищённый от подделки. Он лежит, например, в основе криптовалюты биткоин.

Блокчейн — это действительно последовательность блоков, а в каждом блоке находится некоторая полезная информация. Так последовательность биткоина — список транзакций за определённый период времени: кто, кому, когда и сколько денег передал. Этот список снабжён случайным числом и некоторыми служебными данными, в том числе хэшем — числом, которое по определённой формуле зависит от остальной части блока и хэша предыдущего блока.

Хэш должен быть меньше определённого числа. При этом формула, по которой вычисляется хэш, устроена так, что невозможно получить достаточно маленький хэш иначе, чем перебирая различные значения случайного числа. Поэтому если злоумышленник решит подделать блокчейн — например, вставить в его середину блок с записью о том, что все люди передали ему все свои деньги, — то столкнётся с проблемой. Ему придётся подобрать новое случайное число не только в поддельном блоке, но и во всех последующих, ведь хэш каждого следующего блока зависит от хэша предыдущего.

Это требует невероятно больших вычислительных мощностей, поэтому блокчейн в целом защищён от подобных атак.

Напишите программу, которая проводит проверку правильности хэшей в модельном блокчейне с простой хэш-функцией. Блок b_n​ с номером n включает полезную информацию m_n​, представленную натуральным числом, r_n​ — случайное число от 0 до 255 и h_n​ — хэш (целое число от 0 до 255). У каждого блока хэш вычисляется по формуле h_n​=37×(m_n​+r_n​+h_n−1​) (по модулю 256), при вычислении хэша начального блока h₀​ вместо хэша предыдущего блока берётся ноль. При этом каждый блок представлен одним числом b_n​=h_n​+r_n​×256+m_n​×2562. Также требуется, чтобы хэш h_n​ был меньше 100.

Формат ввода

На первой строке вводится натуральное число N — количество блоков. Далее следуют N чисел b_n​, каждое на отдельной строке.

Формат вывода:

Следует вывести номер первого блока, у которого неправильный хэш (не меньше 100 или не совпадает с вычисленным по указанной в условии формуле), или -1, если все хэши в блокчейне правильные. Нумерация блоков идёт с нуля, так что они имеют номера от 0 до N-1.

Пример

Ввод

5
6122802
14406496
15230209
2541121
1758741

Вывод

-1

Ввод

5
1865535
13479687
16689153
1839958
5214020

Вывод

3

Решение

Задача проще чем кажется из-за костноязычной постановки.

Считаем блоки по формулам, не забывая что для первого блока в списке хэш предыдущего равен нулю.

current_hash = block % 256
r = (block // 256) % 256
m = block // 256 ** 2
new_hash = (37 * (m + r + last_hash)) % 256

Проверям блок на выполнение условий. Если условие не выполнено, запоминаем номер и выводим его. Если мы добрались до конца и не встретили ошибки – выводим -1

q = int(input())

last_hash = 0
err = 0
is_error = False

for i in range(q):
    block = int(input())
    current_hash = block % 256
    r = (block // 256) % 256
    m = block // 256 ** 2
    new_hash = (37 * (m + r + last_hash)) % 256
    if new_hash != current_hash or new_hash >= 100:
        if is_error is False:
            err = i
            is_error = True
    last_hash = current_hash

if is_error is False:
    print(-1)
else:
    print(err)