Count MEX

4.2

14 votes
Algorithms, , Greedy algorithm, Linear Search
Problem

The MEX of an array is the minimum non-negative integer that is not present in it. For example,

  • The MEX of array [2,5,0,1] is 3, because it contains 0,1,2 and 5 but not 3.
  • The MEX of array [1,2,5] is 0, because 0 is the smallest non-negative integer not present in the array.
  • The MEX of array [0,1,2,3] is 4.

You are given a permutation P of the integers {0,1,2,,N1}.

For each i from 1 to N, find the number of subarrays of the permutation P such that the MEX of the subarray is equal to i.

An array B is a subarray of an array A if B can be obtained from aa by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

  Input format

  • The first line of input contains an integer T denoting the number of test cases. The description of each test case is as follows:
  • The first line of each test case contains an integer N denoting the length of the permutation P.
  • The second line of each test case contains N integers P1,P2,,PN, denoting the elements of the permutation P.

Output format

For each test case, print N space-separated integer where the ith integer denotes the number of subarrays of the permutation P such that the MEX of the subarray is equal to i.

Constraints

1T1051N31050PiN1,PiPj for each 1i<jNSum of N over all test cases does not exceed 3105.

 

Sample Input
2
3
2 0 1
5
4 0 2 1 3
Sample Output
2 1 1
4 0 2 1 1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, 

  • The subarrays with MEX = 1 are : [2,0],[0].
  •  The subarray with MEX = 2 is : [0,1]. 

  •  The subarray with MEX = 3 is : [2,0,1].

 

Editor Image

?