Известный пират Джек Воробей и менее известный пират Ферранте Альбрицци, еще менее известный под именем капитан Злой Рок, совместно ограбили испанскую торговую шхуну и решили разделить награбленное. Добыча состоит из n занумерованных предметов, i-ый из которых стоит a_i пиастров.

Пираты решили брать по одному предмету по очереди, причем Джек Воробей берет первым, поскольку он более известен. Но Ферранте Альбрицци не интересуется деньгами, потому что стал пиратом вовсе не из-за них, так что всегда просто берет еще не взятый предмет с наименьшим номером. Джек Воробей отлично знает об этом и решил действовать так, чтобы максимизировать стоимость доставшейся ему добычи. Определите, сколько получит каждый из них.