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

Limits: 1 sec., 256 MiB

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

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

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

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

Input

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

Output

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

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
5 1 2 3 5 7	3 15

Input (stdin) сopy	Output (stdout) сopy
10 100 100 100 100 100 4 4 1 5 4	13 505

Input (stdin) сopy	Output (stdout) сopy
6 100 40 1 5 4 3	9 144