题面描述

小杨有一个包含n个正整数的序列$A=[a_1,a_2,\dots,a_n]$，需要计算有多少对$\langle l,r \rangle$（$1 \le l \le r \le n$）满足$al \times a{l+1} \times \dots \times a_r$为完全平方数。 一个正整数$x$为完全平方数当且仅当存在正整数$y$使得$x=y \times y$。

输入格式

第一行包含一个正整数$n$，代表正整数个数。 第二行包含$n$个正整数$a_1,a_2,\dots,a_n$，代表序列$A$。

输出格式

输出一个整数，代表满足要求的$\langle l,r \rangle$数量。

样例1

输入：

5
3 2 4 3 2

输出：

2

样例解释

满足条件的$\langle l,r \rangle$有$\langle 3,3 \rangle$和$\langle 1,5 \rangle$。

数据范围

对于全部数据，保证$1 \le n \le 10^5$，$1 \le a_i \le 30$。