Занятие 15

Игра между двумя игроками. Дана последовательность из `N` положительных целых чисел (`N` – четное число). Игроки ходят по очереди. Ход заключается в том, что игрок выбирает число, расположенное на левом или на правом конце последовательности. Выбранное число стирается. Игра заканчивается, когда чисел не останется. Первый игрок выигрывает, если сумма выбранных им чисел не меньше, чем сумма чисел, выбранных вторым игроком. Первый игрок всегда ходит первым. Известно, что у первого игрока есть простая выигрышная стратегия, не требующая большого перебора вариантов.

Требуется написать программу, которая реализует выигрышную стратегию первого игрока, т.е. советует левое или правое число следует выбрать.

В первой строке ввода содержится четное целое число `N` (2 ≤ `N` ≤ 32000), во второй строке `N` целых чисел от 1 до 32000.

Вывести "LEFT", если первым ходом нужно взять левое число, или "RIGHT", если правое.

4
4 2 6 3

LEFT