A. Сережа болон Дима

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сережа Дима хоёр тоглож байгаа.Энэ тоглоом нь маш энгийн дүрэмтэй. Тоглогчдод нийт $n$ ширхэг хүзэр байгаа. Хүзэр бүр дээр тоо бичигдсэн байгаа. Тоглогчид тэдгээр хүзрээс авах ба Сережа эхлэнэ. Тоглогч бүр хүзрийн хамгийн баруун тал, эсвэл хамгийн зүүн захаас л хүзэр авах боломжтой. Ямар ч хүзэр үлдээгүй тохиолдолд тоглоом дуусна. Тоглоом дуусхад хэн нь хамгийн их оноо цуглуулна тэр тоглогч хожно.

Сережа болон Дима маш зальтай учраас өөрсдийн нүүдэл бүр дээр хамгийн их тоотой хүзрийг авдаг.

Хүзрийн дараалал өгөгдсөн бол тоглоом дуусахад хэн нь хэдэн оноотой байхыг тооцоол.

Оролт

Эхний мөрөнд хүзрийн тоо болох $n (1 ≤ n ≤ 1000)$ тоо. Хоёр дахь мөрөнд зүүнээс баруун тийш хүзрүүд зайгаар тусгаарлагдан өгөгдөнө. Хүзэр дээрх тоо 1-с 1000н хооронд давтагдахгүй тоо байна.

Гаралт

Нэг мөрөнд хоёр тоо байрлана. Тоглоом дуусахад Сережа болон Димагийн цуглуулсан тооны нийлбэр.

Орчуулсан: Хүрэлцоож

Жишээ тэстүүд

Оролт
4
4 1 2 10
Гаралт
12 5
Оролт
7
1 2 3 4 5 6 7
Гаралт
16 12

Тэмдэглэл

In the first sample Sereja will take cards with numbers $10$ and $2$, so Sereja's sum is $12$. Dima will take cards with numbers $4$ and $1$, so Dima's sum is $5$.

Сэтгэгдлүүдийг ачааллаж байна...