D - 混沌回文

题目描述

我们定义一个长度为 $n$ 的序列 $a$ 是混沌回文的，当且仅当：

存在将 $a$ 内部重排的方式，使得最后对于 $1\le i\le n$ ， $a_i=a_{n+1-i}$ 。

现在给定长度为 $2n$ 的序列 $a$ ，满足 $1$ 到 $n$ 都在 $a$ 中出现恰好两次。

对于 $1\le i\le 2n$ ，你希望求出有多少对整数 $l,r$ 满足：

1. $1\le l\le i\le r\le 2n$ 。

2. $a_i$ 在 $a_l$ 到 $a_r$ 形成的序列中出现了恰好一次。

3. $a_l$ 到 $a_r$ 形成的序列是混沌回文的。

输入格式

第一行输入整数 $n$。

第二行输入 $2n$ 个整数，第 $i$ 个整数代表 $a_i$ 。

输出格式

输出一行 $2n$ 个整数，第 $x$ 个整数代表 $i=x$ 时的答案。

样例

样例输入

4
1 2 4 3 4 1 3 2

样例输出

1 2 1 2 1 3 1 1

数据范围

对于所有数据，$n\le 5*10^5,1\le a_i\le n$ ，$1$ 到 $n$ 的每个数都在 $a$ 中出现恰好两次。

子任务 1 ( 20% ) : $1\le n\le 200$ 。

子任务 2 ( 20% ) : $1\le n\le 2000$ 。

子任务 3 ( 30% ) : 设 $l_i,r_i$ 分别是 $i$ 第一次，第二次出现的位置。则不存在一对 $i\neq j$ 满足 $l_i<l_j<r_i<r_j$ 。

子任务 4 ( 30% ) : 无特殊限制。