【题目描述】

我们定义一个长度为 n 的序列 a 是混沌回文的，当且仅当：

存在将 a 内部重排的方式，使得最后对于 1 ≤ i ≤ n，$ai = a_{n+1-i}$ 。

现在给定长度为 2n 的序列 a ，满足 1 到 n 都在 a 中出现恰好两次。

对于 1 ≤ i ≤ 2n ，你希望求出有多少对整数 l, r 满足：

1. 1 ≤ l ≤ i ≤ r ≤ 2n 。

2. $a_i$ 在 $a_l$ 到 $a_r$ 形成的序列中出现了恰好一次。

3. $a_l$ 到 $a_r$ 形成的序列是混沌回文的。

【输入格式】

第一行输入整数 n。

第二行输入 2n 个整数，第 i 个整数代表 $a_i$ 。

【输出格式】

输出一行 2n 个整数，第 x 个整数代表 i = x 时的答案。

【样例输入】

4
1 2 4 3 4 1 3 2

【样例输出】

1 2 1 2 1 3 1 1

【数据范围】

对于所有数据， n ≤ 5 × 10^5 , 1 ≤ ai ≤ n， 1 到 n 的每个数都在 a 中出现恰好两次。

子任务 1 ( 20% ) : 1 ≤ n ≤ 200 。

子任务 2 ( 20% ) : 1 ≤ n ≤ 2000 。

子任务 3 ( 30% ) : 设 $l_i ,r_i$ 分别是 i 第一次，第二次出现的位置。则对于任意 1 ≤ i < j ≤ n, $[l_i < l_j ] = [r_i > r_j ]$ 。

子任务 4 ( 30% ) : 无特殊限制。