Задача SqStr  “Гарне шифрування - запорука виграшу” - подумав Вася, граючи з рядком з N символів. Для того, щоб зручніше було шифрувати рядок, він перетворив його у послідовність натуральних чисел від 1 до 255. Дуже швидко він придумав прекрасний алгоритм шифрування, який, безумовно, тепер представляє собою державну таємницю, а тому публікувати ми його тут не будемо. Натомість дамо взяти участь у дослідженні властивостей алгоритму. Вася помітив, що алгоритм “гарно” працює на рядках, де добуток кодів символів рівний квадрату деякого натурального числа. Такими рядками є, наприклад, рядки з кодами    (1, 128, 128),  (2, 5, 10), (7, 7, 49). У заданому рядку з N чисел вам необхідно знайти кількість непорожніх підрядків, на яких алгоритм працюватиме “гарно” (тобто підрядки, на яких добуток кодів рівний квадрату деякого натурального числа).

Технічні умови Програма SqStr читає  з пристрою стандартного введення в одному рядку  натуральне число N (N <= 300000) – довжину рядка, а далі через пропуски слідують рівно N натуральних чисел, що за значенням не перевищують 255 - коди символів.

Програма повинна вивести одне ціле число - кількість підрядків, на яких алгоритм працюватиме “гарно”.

 

Введення

Виведення

Коментар

3 1 128 128

3

“гарним” підрядками є (128, 128) та (1, 128, 128), (1)

3 7 7 49

3

“гарними” підрядками є (7, 7), (49), (7, 7, 49)

4 1 2 2 1

6

“гарними” підрядками є (1), (1), (2, 2), (1, 2, 2), (2, 2, 1), (1, 2, 2, 1)

Зверніть увагу, що підрядок (1) у рядку зустрічається двічі, тому і враховується двічі.

© LIKT 1998-2018