有一堆共 $2N$ 个立方体。每个立方体都被分配了一个介于 $1$ 到 $N$ 之间的整数，该数字标记在立方体的每个面上。每个数字都恰好写在两个立方体上。立方体一个叠在一个上面，排成一叠。如果两个写有相同数字的立方体相邻，它们就会消去：两个立方体都消失，上方的立方体下落以填补空缺。

你的任务是拆除这一叠立方体——消去所有的立方体。你被允许交换任意两个相邻的立方体。只有在所有可能的消去都完成后，才能进行交换。

例如，如果 $N=4$ 且立方体排列如下（从上到下）：

2
4
1
3
3
4
1
2

那么你需要进行一次交换。标记为 $3$ 的立方体立即消去；你交换从下往上数第 $4$ 个立方体（标记为 $1$）和第 $5$ 个立方体（标记为 $4$）；之后，标记为 $4$ 的立方体消去，接着是标记为 $1$ 和标记为 $2$ 的立方体。另一种选择是交换从下往上数第 $3$ 个和第 $4$ 个立方体（在这种情况下，标记为 $1$ 和 $4$ 的立方体同时消去，接着是标记为 $2$ 的立方体），或者交换第 $2$ 个和第 $3$ 个。

如果 $N=3$ 且立方体排列如下（从上到下）：

2
3
1
2
3
1

你需要进行 $3$ 次交换。一种解决方法是交换第 $5$ 个和第 $6$ 个立方体（从下往上数），然后交换第 $4$ 个和第 $5$ 个；标记为 $2$ 的立方体消去；然后交换第 $2$ 个和第 $3$ 个；其余立方体同时消去。

任务是求出消去所有立方体所需的最少交换次数。

输入格式

输入的第一行包含一个正整数 $N$（$2 \le N \le 100\,000$）。

第二行包含所有立方体的标记，从下往上，用空格隔开。

输出格式

输出的唯一一行应包含一个非负整数 $M$ — 销毁所有立方体所需的最少交换次数。

样例

输入样例 1

4
2 1 4 3 3 1 4 2

输出样例 1

1

输入样例 2

3
1 3 2 1 3 2

输出样例 2

3

输入样例 3

3
1 3 2 2 3 1

输出样例 3

0