D2 - Queue

配点 : 450点

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

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

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

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

• 入力はすべて整数

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

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

• 入力

10
4 1 1 3 3 2 1 2 3 1

• 出力

3

操作の一例を示します。

• 1つめの操作を行う。
  筒: 種類数:、箱: 種類数:
• 2つめのを行う。
  筒: 種類数:、箱: 種類数:
• 2つめの操作を行う。
  筒: 種類数:、箱: 種類数:

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

• 入力

4
1 1 1 1

• 出力

1

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

• 入力

7
1 2 3 4 5 6 7

• 出力

-1

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