Задача 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) у рядку зустрічається двічі, тому і враховується двічі. |