Однажды после очередного написанного соревнования по программированию Петя и Гена решили поиграть в какую-нибудь игру. Так как большинство современных игр кажутся им достаточно скучными, они любят придумывать свои собственные. В доступности нашлись только стикеры и ручки, но это их не остановило.

Они придумали следующую игру. Изначально они расклеили n стикеров в ряд на стене и написали на каждом стикере своё число. Далее они стали совершать ходы по очереди, причём Петя ходит первым.

В течение каждого хода происходит следующее. Пусть на стене сейчас висит m ≥ 2 стикеров. Игрок, которых ходит в данный момент, выбирает целое число k от 2 до m и забирает k стикеров с левого конца ряда себе. После этого он клеит новый стикер с левого конца ряда и пишет на нём число, равное сумме всех чисел на стикерах, которые он забрал себе на этом ходу.

Игра заканчивается, как только на стене остаётся один-единственный стикер. Счёт игрока определяется как сумма чисел, написанных на всех стикерах, которые он забрал себе. Каждый игрок стремится максимизировать разницу между своим количеством очков и количеством очков соперника.

Конечно же, Петя и Гена вкладывают другой смысл в понятие «играть в игру», нежели мы привыкли себе думать. Они уже разобрались, как по значению n и числам, написанным на каждом из стикеров исходно, определить разницу между Петиными и Гениными очками, если они будут играть оптимально. Справитесь ли вы с той же самой задачей?