如果一个长度为 $M$ 的序列 $B = (B_1, B_2, \dots, B_M)$ 满足对于所有 $i = 1, 2, \dots, M$ 都有 $B_i = B_{M+1-i}$，则称其为回文序列。

如果一个序列 $B$ 存在一个排列是回文序列，则称其为伪回文序列。

给定一个长度为 $2N$ 的序列 $A = (A_1, A_2, \dots, A_{2N})$，其中 $1$ 到 $N$ 的每个数字恰好出现两次。

对于每个 $i = 1, 2, \dots, 2N$，计算满足以下条件的整数对 $(l, r)$ ($1 \le l \le r \le 2N$) 的数量：

1. $l \le i \le r$
2. 数字 $A_i$ 在 $(A_l, A_{l+1}, \dots, A_r)$ 中恰好出现一次。
3. $(A_l, A_{l+1}, \dots, A_r)$ 是一个伪回文序列。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1 \ A_2 \ \dots \ A_{2N}$

• $1 \le N \le 5 \times 10^5$
• $1, 2, \dots, N$ 中的每个数字在 $A$ 中恰好出现两次。
• 所有输入值均为整数。

输出格式

令 $X_i$ 表示第 $i$ 个问题的答案。按顺序输出 $X_1, X_2, \dots, X_{2N}$，中间用空格分隔。

样例

样例输入 1

2
1 1 2 2

样例输出 1

1 2 2 1

样例输入 2

3
2 1 2 3 1 3

样例输出 2

1 2 2 2 2 1

样例输入 3

4
1 2 4 3 4 1 3 2

样例输出 3

1 2 1 2 1 3 1 1

样例输入 4

1
1 1

样例输出 4

1 1

说明

在第一个样例中，对于每个 $i$ 满足条件的对为：

• $i = 1: (1, 1)$
• $i = 2: (2, 2), (2, 4)$
• $i = 3: (1, 3), (3, 3)$
• $i = 4: (4, 4)$