SirCOX

Time limit: 1s Memory limit: 64MB Input: Output:

Cerință

Se da un sir AA de NN valori, din acest sir putem alege oricare 22 elemente alaturate cu valori egale si sa le unim intr-un element cu valoare cu 11 mai mare.
Care e lungimea minima la care pot aduce sirul astefel incat sa fie un sir COXCOX?
Un sir COXCOX este un sir in care xor-ul oricaror doua elemente alaturate sa aiba numar impar de biti de 11.
De exemplu elementele 11 si 33 pot sta alaturate intr-un sir COXCOX deoarece 13=21 \oplus 3 = 2, iar 22 are numar impar de biti de 11 (are 11 bit).

Date de intrare

Pe prima linie il avem pe NN.
Pe a doua linie este sirul AA.

Date de ieșire

Lungimea minima a unui sir COXCOX la care putem ajunge sau 1-1 daca nu putem ajunge la niciun sir COXCOX.

Restricții și precizări

  • 1N1031 \leq N \leq 10^3
  • 1Ai201 \leq A_i \leq 20
  • Un sir care contine un singur element este considerat COXCOX.
  • Problema admite doar solutii de 100100 de puncte.

Exemplul 1

stdin

5
1 2 1 1 2

stdout

3

Explicație

Lungimea minima este 33 si o obtinem asa:

(1,2,1,1,2)>(1,2,2,2)>(1,3,2)(1, 2, 1, 1, 2) -> (1, 2, 2, 2) -> (1, 3, 2).

Exemplul 2

stdin

4
2 1 1 5

stdout

-1

Explicație

Nu putem obtine un sir COXCOX.

Log in or sign up to be able to send submissions!