Count Pseudo-Palindromes
对于长度为 M 的序列 B=(B1,B2,…,BM),如果对所有 1≤i≤M 都有 Bi=BM+1−i,则称 B 是回文序列。
如果能够将 B 的元素重新排列,使其成为回文序列,则称 B 是伪回文序列。
给定一个长度为 2N 的序列 A=(A1,A2,…,A2N),其中 1,2,…,N 中的每个数恰好出现两次。
对于每个 i=1,2,…,2N,求满足以下全部条件的整数对 (l,r) 的数量:
- 1≤l≤i≤r≤2N;
- 数字 Ai 在子序列 (Al,Al+1,…,Ar) 中恰好出现一次;
- (Al,Al+1,…,Ar) 是伪回文序列。
输入格式
N
A_1 A_2 ... A_{2N}
所有输入均为整数,满足:
- 1≤N≤5×105;
- 1,2,…,N 中的每个数在 A 中恰好出现两次。
输入只有一组数据。
输出格式
设第 i 个位置对应的答案为 Xi,按顺序输出 X1,X2,…,X2N,用空格分隔。
样例 1
输入
2
1 1 2 2
输出
1 2 2 1
说明
每个位置对应的合法 (l,r) 如下:
- i=1:(1,1);
- i=2:(2,2)、(2,4);
- i=3:(1,3)、(3,3);
- i=4:(4,4)。
样例 2
输入
3
2 1 2 3 1 3
输出
1 2 2 2 2 1
样例 3
输入
4
1 2 4 3 4 1 3 2
输出
1 2 1 2 1 3 1 1
样例 4
输入
1
1 1
输出
1 1