Задача Красивая Ленточка

помогите решить, пожалуйста


Красивая Ленточка
ограничение по времени на тест2 s.
ограничение по памяти на тест256 MB
Вот уже полчаса все внимание Михаила занимает ленточка, найденная им в ящике стола. Миша подметил, что ленточка состоит из N кусочков различных цветов, последовательно соединенных друг с другом.

Мише кажется, что лента является по-настоящему красивой, если все ее кусочки можно разбить на пары так, чтобы цвета кусочков в каждой паре были бы одинаковыми. Например, ленточка, состоящая из кусочков с цветами 1, 2, 10, 1, 2, 10, 1, 1, является красивой, а ленточка с цветами 1, 2, 1 — нет.

Теперь Миша хочет разрезать ленту на минимальное количество отрезков так, чтобы каждый отрезок по отдельности представлял из себя красивую ленту. Также Миша понимает, что, возможно, так разрезать ленту не удастся. От вас требуется посчитать искомое минимальное количество отрезков или сообщить, что разрезать ленту нужным образом невозможно.

Входные данные
В первой строке входных данных записано целое число N(1≤N≤200000) — количество кусочков, из которых состоит лента.

В следующей строке записано N целых чисел c1,c2,…,cN (1≤ci≤109) — цвета кусочков ленты в порядке слева направо.

Выходные данные
В единственной строке выведите одно число — минимальное количество отрезков, на которое нужно разрезать ленту, чтобы каждый отрезок по отдельности являлся красивым.

Если разрезать ленту требуемым образом невозможно, выведите число «-1» (без кавычек).

Примеры
Входные данные
8
1 2 10 1 2 10 1 1
Выходные данные
1

Входные данные
2
1 2
Выходные данные
-1
Примечание
Лента, приведенная в первом примере, сама по себе является красивой (что было описано выше), значит ее не придется резать. Таким образом, количество отрезков равно одному.

Лента из второго примера не является красивой, и ее невозможно разрезать на красивые отрезки.

0

В такой постановке задача сводится просто к подсчёту символов. Если соединить две красивые ленточки, получится снова красивая ленточка. Так что: если каждый символ встречается чётное число раз, ответ — 1, если нет — -1.

0

iifat, а для такой ленты 111222333 какой ответ будет?

0

-1, естественно. У вас что-то другое получается?

0