The MEX of an array is the minimum non-negative integer that is not present in it. For example,
You are given a permutation of the integers .
For each from to , find the number of subarrays of the permutation such that the MEX of the subarray is equal to
An array is a subarray of an array if 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
Output format
For each test case, print space-separated integer where the integer denotes the number of subarrays of the permutation such that the MEX of the subarray is equal to
Constraints
In the first test case,
The subarray with MEX = is :
The subarray with MEX = is : .