Dat je niz prirodnih brojeva ~S~ sa ~N~ elemenata. Da li u nizu ~S~ postoji patern ~A B A B~ ?

Kažemo da u nizu ~S~ postoji patern ~A B A B~ ako postoje četiri indeksa ~(e, f, g, h)~ i uređeni par ~(X, Y)~ tako da važi:

• ~ 1 \leq e < f < g < h \leq N ~
• ~S_e = S_g = X~ i ~S_f = S_h = Y~
• ~X \neq Y~

Ako postoji više uređenih parova ~(X, Y)~ koji zadovoljavaju ~A B A B~ patern, potrebno je naći najmanji leksikografski par (uzeti par koji ima minimalnu vrednost elementa ~X~, ako i dalje postoji više mogućih parova uzeti onaj koji minimizuje vrednost elementa ~Y~).

Opis ulaza

• U prvoj liniji standardnog ulaza, učitati prirodan broj ~N \leq 400 000~, broj elemenata u nizu ~S~.
• U svakoj od ~N~ narednih linija standardnog ulaza učitati po jedan prirodan broj, u ~i~-toj liniji učitati broj ~S_i \leq N~.

Opis izalza

U jedinoj liniji standardnog izlaza ispisati najmanji leksikografski uređeni par ~(X, Y)~ koji zadovoljava ~A B A B~ patern, ako takav par ne postoji ispisati ~-1~.

Primer ulaza

4
2 
1 
2
1

Primer izlaza

2 1

Primer ulaza

8
1
2
3
4
5
6
7
1

Primer izlaza

-1

Objašnjenje primera

Obratite pažnju da govorimo o uređenim parovima tako da odgovor ~(1, 2)~ u prvom primeru ne bi bio pravilan.

U drugom primeru jedino se broj ~1~ javlja dva puta u nizu ~S~, tako da nema rešenja.