Tânărul Pagnad își dorește foarte mult să se poată juca jocul lui preferat, dar pe mama lui a apucat-o curățenia prin casă. După ce s-au împărțit sarcinile el a rămas să facă curat la papuci. Acesta are papucii așezați pe două etajere, fiecare papuc are pereche. Acesta poate efectua două tipuri de operații asupra papucilor, poate să ridice un papuc și să-l pună într-un anumit loc sau să împingă un papuc.
Pagnad trebuie să aranjeze papucii astfel încât fiecare papuc să aibe perechea lângă el. Deoarece acesta este un leneș, își dorește să ridice greutăți cât mai mici, deoarece fiecare papuc este caracterizat printr-o greutate. Aflați care este greutatea maximă pe care trebuie să o ridice Pagdan. Se consideră că fiecare pereche are greutăți diferite și că nu există două perechi asemănătoare.
Cerința
Se cere greutatea maxima pe care trebuie sa o ridice Pagdan.
Date de intrare
Fișierul de intrare gr.in
conține pe prima linie n
numărul de papuci, vor urma doua linii, fiecare cu n
numere reprezentând greutățile papucilor.
Date de ieșire
Fișierul de ieșire gr.out
va conține un singur număr, reprezentând greutatea maximă care trebuie ridicată.
Restricții și precizări
1 ≤ n ≤ 1.000.000
- greutățile papucilor sunt numere naturale ≤
10
9
.
Exemplu:
gr.in
5 2 1 8 2 8 9 9 4 1 4
gr.out
2
Explicație
Acesta va muta papucul de greutate 1
de pe raftul 2
pe raftul 1
și papucul de greutate 2
aflat pe poziția 4
de pe raftul 1
lângă primul papuc de greutate 2
.