You are given an array $$$A$$$ of $$$N$$$ integers, where $$$A_i$$$ denotes the height of the $$$i^{th}$$$ person in the line. For each person, they wish to compare with those who stood before them — including themselves.
For each position $$$i$$$, compute the average height of all people in the prefix $$$[1, i]$$$ whose height is greater than or equal to $$$A_i$$$.
Your task is to compute this value for every position with modulo $$$10^9+7$$$.
The first line contains a single integer $$$N (1 \leq N \leq 2⋅10^5)$$$, the number of people in the line.
The second line contains $$$N$$$ space-separated integers $$$A_1, A_2, \ldots, A_N$$$ $$$(1 \leq A_i \leq 10^{15})$$$, the heights of the people.
Print $$$N$$$ space-separated integers, where the $$$i^{th}$$$ number is the average described above for position $$$i$$$.
5 5 1 8 2 5
5 3 8 5 6
In the sample testcase:
When, $$$i = 1 → \frac{5}{1} = 5$$$
When, $$$i = 2 → \frac{5+1}{2} = 3$$$
When, $$$i = 3 → \frac{8}{1} = 8$$$
When, $$$i = 4 → \frac{5+8+2}{3} = 5$$$
When, $$$i = 5 → \frac{5+8+5}{3} = 6$$$
