Поганий програміст

Обмеження: 1 сек., 256 МіБ

Після кожної успішної “справи” ви з напарником ділите між собою здобич.

Вона виглядає як \(N\) мішків складених в ряд. Принцип поділу виглядає так:

Ваш напарник починає першим, мішки лежать у ряд. Ви по черзі ділите мішки що залишились на 2 половини (міняти місцями мішки не можна) (у випадку якщо їх непарна кількість — середній мішок йде в ліву купу) і забираєте собі половину з більшою сумарною масою. Якщо при поділі маси куп вийшли рівні — ви забираєте собі ліву.

Ваш напарник — поганий програміст, чого не можна сказати про вас, тому ви вирішили написати програму, яка буде говорити вам скільки золота буде в купі кожного ковбоя після поділу (спочатку меншу).

Вхідні дані

У першому рядку задано ціле число \(N\) — кількість мішків з золотом. У другому рядку задано \(N\) додатніх цілих чисел — кількість золота у кожному мішку.

Вихідні дані

Виведіть два цілих числа — скільки золота буде в двох купах, у порядку зростання.

Обмеження

\(1 \le N \le 10^5\),

\(1 \le a_i \le 100\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 2 3 5 7	3 15

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
10 100 100 100 100 100 4 4 1 5 4	13 505

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 100 40 1 5 4 3	9 144