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.