Перо е одличен ученик во едно основно училиште, и голем љубител на математиката. Бидејќи неговата наставничка не му дава доволно домашни задачи, тој пронашол интересна игра со низи од броеви, за да го исполни своето слободно време.

Играта започнува со давање низа од N цели броеви (N е делив со 3), и притоа играчот (во нашиот случај Перо) треба да исфрли една третина од броевите во низата, без да ги измести или премести останатите броеви.

Од кога ќе го направи тоа, се добива низа каде што остануваат две третини од елементите (бидејќи во првиот чекор се исфрлија една третина од елементите во оригиналната низа). Сега, нека ја поделиме оваа ново добиена низа на два дела со по ист број на елементи (лев и десен дел), и нека го означиме збирот на елементите во левиот дел со A, и збирот на елементите во десниот дел со B. Поените кои што Перо ги добива во играта е разликата (A-B).

Перо често се прашува дали ги избрал вистинските елементи за исфрлање, за да ја постигне максималната можна вредност на разликата (A-B). Напишете програма која ја наоѓа максималната можна вредност на (A-B).

Влез

Во првиот ред е запишан еден цел број N (3 <= N <= 300 000), кој го означува бројот на елементи во оригиналната низа, и овој број секогаш ќе биде делив со 3.

Во вториот ред се запишани N цели броеви Xi (1 <= Xi <= 1000000).

Забелешка: Во тест случаи кои носат најмалку 15% од поените, бројот N ќе биде еднаков на 3. Во други тест случаи кои носат најмалку 30% од поените, бројот N ќе биде помал или еднаков на 15.

Излез

Во еден ред се запишува бараната максимална вредност на разликата (A-B).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3
5 1 3

излез
4

влез
9
12 6 6 11 8 10 9 7 12

излез
5

Објаснување за првиот тест пример: доколку се исфрли 5 разликата ќе биде -2 (1-3); доколку се исфрли 1 разликата ќе биде 2 (5-3), а доколку се исфрли 3 разликата ќе биде 4 (5-1).

Објаснување за вториот тест пример: Доколку се исфрлат двете 6-ки и последната 12-ка, ќе останат елементите [12, 11, 8, 10, 9, 7]. Во оваа ново добиена низа, збирот на елементите во левата половина е 31 (12+11+8), збирот на елементите во десната половина е 26 (10+9+7), и нивната разлика e 5 (31-26).