#P18199. Count Pseudo-Palindromes

Count Pseudo-Palindromes

Count Pseudo-Palindromes

对于长度为 MM 的序列 B=(B1,B2,…,BM)B=(B_1,B_2,\ldots,B_M),如果对所有 1≤i≤M1\le i\le M 都有 Bi=BM+1−iB_i=B_{M+1-i},则称 BB 是回文序列。

如果能够将 BB 的元素重新排列,使其成为回文序列,则称 BB 是伪回文序列。

给定一个长度为 2N2N 的序列 A=(A1,A2,…,A2N)A=(A_1,A_2,\ldots,A_{2N}),其中 1,2,…,N1,2,\ldots,N 中的每个数恰好出现两次。

对于每个 i=1,2,…,2Ni=1,2,\ldots,2N,求满足以下全部条件的整数对 (l,r)(l,r) 的数量:

  1. 1≤l≤i≤r≤2N1\le l\le i\le r\le2N;
  2. 数字 AiA_i 在子序列 (Al,Al+1,…,Ar)(A_l,A_{l+1},\ldots,A_r) 中恰好出现一次;
  3. (Al,Al+1,…,Ar)(A_l,A_{l+1},\ldots,A_r) 是伪回文序列。

输入格式

N
A_1 A_2 ... A_{2N}

所有输入均为整数,满足:

  • 1≤N≤5×1051\le N\le5\times10^5;
  • 1,2,…,N1,2,\ldots,N 中的每个数在 AA 中恰好出现两次。

输入只有一组数据。

输出格式

设第 ii 个位置对应的答案为 XiX_i,按顺序输出 X1,X2,…,X2NX_1,X_2,\ldots,X_{2N},用空格分隔。

样例 1

输入

2
1 1 2 2

输出

1 2 2 1

说明

每个位置对应的合法 (l,r)(l,r) 如下:

  • i=1i=1:(1,1)(1,1);
  • i=2i=2:(2,2)(2,2)、(2,4)(2,4);
  • i=3i=3:(1,3)(1,3)、(3,3)(3,3);
  • i=4i=4:(4,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