Question
Ram's Assignment
Ram in his maths class was given an assignment. The assignment was as follows, given a permutation P of length N. For each 1 ≤ i ≤ N, He needs to find the number of subarrays of P with sum i.
Note: That a permutation of length N consists of all integers from 1 to N exactly once.
Input
The first line contains a single integer T, denoting the number of test cases.
The first line of each test case contains a positive integer N - the length of P.
The second line contains N space separated distinct integers, denoting the permutation P.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 2*105
1 ≤ Pi ≤ N
Pi ≠ Pj if i ≠ j.
Note: The sum of N over all test cases won't exceed 2x105
The first line of each test case contains a positive integer N - the length of P.
The second line contains N space separated distinct integers, denoting the permutation P.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 2*105
1 ≤ Pi ≤ N
Pi ≠ Pj if i ≠ j.
Note: The sum of N over all test cases won't exceed 2x105
Output
For each test case, output on a new line, N space-separated integers, where the ith integer denotes the number of subarrays with sum i.
Example
Sample Input
3
1
1
2
1 2
3
3 1 2
Sample Output
1
1 1
1 1 2
Explanation
Test case 1: The only subarray is [1] with sum 1.
Test case 2: For sum 1, the only possible subarray is [1] and for sum 2, the only possible subarray is [2].
3
1
1
2
1 2
3
3 1 2
Sample Output
1
1 1
1 1 2
Explanation
Test case 1: The only subarray is [1] with sum 1.
Test case 2: For sum 1, the only possible subarray is [1] and for sum 2, the only possible subarray is [2].