P12716 [Algo Beat Contest 002 C] Counting Square Numbers

| Problem | Score | Idea | Std | Data | Check | Solution | | :----------------------------------: | :---: | :---------------------------------------------------: | :---------------------------------------------------: | :---------------------------------------------: | :-------------------------------------------------: | :----------------------------------------------------------: | | $\text{C - Counting Square Numbers}$ | $300$ | [wenqinghua1001](https://www.luogu.com.cn/user/976198) | [wenqinghua1001](https://www.luogu.com.cn/user/976198) | [joe_zxq](https://www.luogu.com.cn/user/623577) | [joe_zxq](https://www.luogu.com.cn/user/623577) | [Link](https://www.luogu.com.cn/article/75je5m51) by [joe_zxq](https://www.luogu.com.cn/user/623577) |

wtr1 和 wqh 是一对好朋友。 wqh 给了 wtr1 一个长度为 $n$ 的数组 $A$。对于 $i=1,2,\dots,n$，需要 wtr1 给出包含了位置 $i$ 且区间和为完全平方数的子数组个数。由于最近 wtr1 很忙，请聪明的你帮帮他吧！ 若一个数是一个整数的平方，则称这个数是**完全平方数**。 原数组中某段下标连续的元素按原顺序构成的数组称为**子数组**。

第一行输入一个正整数 $n$，表示数组 $A$ 的长度。 第二行输入 $n$ 个整数 $A_1,\dots,A_n$，表示 $A$ 中的元素。

输出 $n$ 行，每行包含一个非负整数，表示符合条件的区间数。

**【样例解释 #1】** 包含位置 $2$ 的区间和为完全平方数是 $2+3+4=9$，只有 $1$ 个。 包含位置 $4$ 的区间和为完全平方数是 $2+3+4=9$，$4+5=9$ 以及 $4$ 本身，共 $3$ 个。 **【数据范围】** - $1 \le n \le 5 \times 10^3$。 - $0 \le a_i \le 10^9$。