题目描述

小杨有一个包含 n 个正整数的序列 a。 小杨想知道有多少对 (i, j) 满足 1 ≤ i ≤ j ≤ n，使得 a[i] * a[i+1] * ... * a[j] 为完全平方数。 一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 y*y == x。

输入格式

第一行包含一个正整数 n，代表正整数个数。 第二行包含 n 个正整数 a[i]，代表序列 a。

输出格式

输出一个整数，代表满足要求的 (i, j) 数量。

样例 1

输入：

5
3 2 4 3 2

输出：

2

样例解释：满足条件的 (i, j) 有 (3, 3) 和 (1, 5)。

数据范围

对于全部数据，保证有 1 ≤ n ≤ 10^5，1 ≤ a[i] ≤ 10^9。