D2 - Queue

配点 : 450点

問題文

筒と箱があり、筒には正整数が書かれたボールが $N$ 個入っており、左から整数 $A_1, A_2 ... A_N$ が書かれています。また、最初箱は空です。

くしらくんは以下の2種類の操作を筒にボールがある限り行い筒と箱に入っているボールに書かれている数字の種類数を同じにしたいです。

• 筒の左からボールをひとつ取り出し、箱Bに入れる。
• 筒の右からボールをひとつ取り出し、箱Bに入れる。

くしらくんが目標を達成することが出来るか判定をし、出来るなら操作の最小回数を答えてください。

制約

• $1≦N≦2×10^5$
• $1≦A_i≦10^9$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

目標を達成できないなら-1、達成できるなら操作の最小回数を答えてください。

入出力例1

• 入力

10
4 1 1 3 3 2 1 2 3 1

• 出力

3

操作の一例を示します。

• 1つめの操作を行う。
  筒:$[1,1,3,3,2,1,2,3,1]$ 種類数:$3$、箱:$[4]$ 種類数:$1$
• 2つめのを行う。
  筒:$[1,1,3,3,2,1,2,3]$ 種類数:$3$、箱:$[4,1]$ 種類数:$2$
• 2つめの操作を行う。
  筒:$[1,1,3,3,2,1,2]$ 種類数:$3$、箱:$[4,1,3]$ 種類数:$3$

操作回数を $3$ 回よりも少なくすることは出来ないので、$3$ を出力します。

入出力例2

• 入力

4
1 1 1 1

• 出力

1

どちらの操作をしても目標を達成することができます。

入出力例3

• 入力

7
1 2 3 4 5 6 7

• 出力

-1

目標を達成することができません。