問題文

長さ 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) は擬回文である

制約

• 1 \le N \le 5 \times 10^5
• 各 1,2,\dots,N は A にちょうど 2 つ含まれる
• 入力はすべて整数

入力例 1

2
1 1 2 2

出力例 1

1 2 2 1

各 i に対して、条件を満たす正整数の組は以下のとおりです。

• 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

出力例 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