题面描述

小杨有一个包含n个正整数的序列A=[a₁,a₂,...,aₙ]。 小杨想知道有多少对<l,r>（1≤l≤r≤n）满足 $al \times a{l+1} \times \dots \times a_r$ 为完全平方数。 一个正整数x为完全平方数当且仅当存在一个正整数y使得x=y×y。

输入格式

第一行包含一个正整数n，代表正整数个数。 第二行包含n个正整数 a₁,a₂,...,aₙ，代表序列 A。

样例1

输入

5
3 2 4 3 2

输出

2

样例解释

满足条件的<l,r> 有 <3,3>和 <1,5>。

数据范围

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