Description

给定一个长度为\(n\)的随机排列\(a_i\)，问对于\(k = 0, 1, 2,..., n-1\)，有多少个子区间满足最大值和最小值的差小于等于\(k\)。

Input

• 第一行一个正整数\(1\le n\le 100000\)。
• 第二行有\(n\)个数，表示\(a_1, a_2, ..., a_n\)。

Output

• 一行\(n\)个数，分别为\(k=0,1,2,..., n-1\)时，最大值和最小值的差小于等于\(k\)的子串的个数。

Sample

Input

4
1 3 2 4

Output

4 5 9 10

Hint

• 对于\(10\)组数据，\(n\)分别为\(10, 50, 100, 2000, 3000, 5000, 50000, 100000, 100000, 100000\)。