Програмчлалын олимпиадын бодлогын архив

Бондод тус бүр дээр нь ямар нэг тоо бичсэн n ширхэг карт байгаа. Тэр хөрш хос картын нийлбэрийн хамгийн их утга нь хамгийн бага байхаар картуудыг цувуулж тавих ёстой.

Input

Эхний мөрөнд n тоо өгөгдөнө (2 ≤ n ≤ 239017). Хоёр дахь мөрөнд модулиараа 1000000000-аас хэтрэхгүй n ширхэг тоонууд байрлана.

Output

Гаралтан дээр Бондын тавьсан дарааллын үе дэх хөрш хос картын нийлбэрийн хамгийн их утгыг хэвлэнэ.

Example

Input:
9
-5 -3 -2 0 1 2 3 3 1

Output:
1
Тайлбар: 3 -5 3 -3 2 -2 1 0 1