AT_tupc2023_h Count Pseudo-Palindromes

长度为 $M$ 的数列 $B=(B_1,B_2,\dots,B_M)$ 被称为**回文**，当且仅当对于所有 $i=1,2,\dots,M$ 都满足 $B_i=B_{M+1-i}$。 又，数列 $B$ 被称为**伪回文**，当且仅当 $B$ 可以通过重新排列变成回文。 --- 给定一个长度为 $2N$ 的数列 $A=(A_1,A_2,\dots,A_{2N})$。$A$ 中包含 $1,2,\dots,N$，每个数字恰好出现 $2$ 次。 对于每个 $i=1,2,\dots,2N$，请计算满足以下条件的正整数组 $(l,r)\ (1 \le l \le r \le 2N)$ 的个数： - $l \leq i \leq r$ - 在 $(A_l,A_{l+1},\dots,A_r)$ 中，$A_i$ 只出现一次 - $(A_l,A_{l+1},\dots,A_r)$ 是伪回文

输入按如下格式从标准输入读入。 > $N$ $A_1$ $A_2$ $\dots$ $A_{2N}$

设第 $i$ 项的答案为 $X_i$，请按顺序用空格分隔输出 $X_1,X_2,\dots,X_{2N}$。

### 样例解释 1 对于每个 $i$，满足条件的正整数组如下： - $i=1$ ：$(1,1)$ - $i=2$ ：$(2,2),(2,4)$ - $i=3$ ：$(1,3),(3,3)$ - $i=4$ ：$(4,4)$ ### 数据范围 - $1 \le N \le 5 \times 10^5$ - $1,2,\dots,N$ 各自恰好在 $A$ 中出现两次 - 所有输入均为整数。 由 ChatGPT 5 翻译