题目描述

小明有一个长度为 $n$ 的序列，其中第 $i$ 个数的权值为 $a_i$。 如果一个区间满足区间权值总和乘以区间的长度小于等于该区间的最大值的平方，那么小明称这个区间叫做幸运区间。 现在问题来了，小明想知道每个前缀 $[1, i]$ $(1 \le i\le n)$ 内幸运区间的个数，你能帮帮他吗？

输入格式

第一行一个整数 $n$，分别表示序列长度。 第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$，表示第 $i$ 个数的权值。

输出格式

输出 $n$ 行，每行输出一个整数，第 $i$ 行的整数表示前缀 $[1, i]$ 内的幸运区间个数。

样例数据

样例输入

3
2 1 3

样例输出

1
2
4

样例解释

只有区间 $[1, 1] [2, 2] [2, 3] [3, 3]$ 是幸运区间，所以区间 $[1, 1]$ 内幸运区间个数为 $1$，区间 $[1, 2]$ 内幸运区间个数为 $2$， 区间 $[1, 3]$ 内幸运区间个数为 $4$。

数据范围

1. 对于 20% 的测试点，满足 $1 \le n \le 5000$；
2. 对于 60% 的测试点，满足 $1 \le n \le 4 \times 10^4$；
3. 对于 100% 的测试点，满足 $1 \le n \le 2 \times 10^5,0 \le a_i \le 10^9$

simple