AT_tupc2023_h Count Pseudo-Palindromes

長さ $ M $ の数列 $ B=(B_1,B_2,\dots,B_M) $ が **回文** であるとは、 $ B_i=B_{M+1-i} $ がすべての $ i=1,2,\dots,M $ について成り立つことをいいます。 また、数列 $ 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 $ は $ 1 $ つだけ含まれる - $ (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} $ をこの順に空白区切りで出力せよ。

### Sample Explanation 1 各 $ i $ に対して、条件を満たす正整数の組は以下のとおりです。 - $ i=1 $ : $ (1,1) $ - $ i=2 $ : $ (2,2),(2,4) $ - $ i=3 $ : $ (1,3),(3,3) $ - $ i=4 $ : $ (4,4) $ ### Constraints - $ 1 \le N \le 5 \times 10^5 $ - 各 $ 1,2,\dots,N $ は $ A $ にちょうど $ 2 $ つ含まれる - 入力はすべて整数