T545111 「YAC Round 13」樱花树下的欲望之果

 噗噗哟果会导致人的欲望无限增加，出现精神失常等副作用。 但是不幸的是，贪吃的西行寺幽幽子吃下了噗噗哟果......

米斯蒂娅有 $n$ 个食材，从 $1$ 到 $n$ 排成一排，每个食材有一个美味值 $a_i$。 米斯蒂娅可以选择一个区间内的所有食材制作美味料理来满足幽幽子的食欲。 当一个区间 $[l, r]$ $(1 \le l \le r \le n)$ 内的所有食材美味值的 **乘积** （即 $\prod_{i = l}^{r}a_i$）是一个 **完全平方数** 时，制作出的美味料理会解除噗噗哟果造成的副作用。 幽幽子是米斯蒂娅的居酒屋的常客，也是她的好朋友，她想要解除幽幽子身上噗噗哟果的副作用。 请你计算一共有多少种选择区间 $[l, r]$ $(1 \le l \le r \le n)$ 的方案可以使得米斯蒂娅拯救幽幽子。

第一行输入一个正整数 $n$（$1 \le n \le 10^5$），代表食材个数。 第二行输入 $n$ 个正整数 $a_i$（$1 \le a_i \le 30$），代表每个食材的美味值。

输出一个整数，代表满足要求的区间 $[l,r]$ 的数量。

共有 $4$ 种选择区间的方案，可以选择区间 $[1, 4]$, $[2, 3]$, $[2, 2]$, $[3, 3]$。