Interviewstreet- Permutation Game

Алиса и Боб играют в следующую игру:

1) Для начала они выбирают перестановку первых N чисел.

2) Они играют по очереди, и Алиса играет первой.

3) В свой ход они могут удалить любое одно оставшееся число из перестановки.

4) Игра заканчивается, когда оставшиеся числа образуют возрастающую последовательность. Выигрывает тот, кто сыграл последний ход (после которого последовательность становится возрастающей).

Если предположить, что оба играют оптимально, кто выиграет игру?

Ввод: Первая строка содержит количество тестовых случаев T. Далее следуют T тестовых случаев. Каждый случай содержит целое число N в первой строке, за которым следует перестановка целых чисел 1..N во второй строке.

Выход: Выведите T строк, по одной для каждого набора входных данных, содержащих «Алиса», если Алиса выигрывает игру, и «Боб» в противном случае.

Пример ввода:

2

3

1 3 2

5

5 3 2 1 4

Пример вывода:

Алиса

Боб

Ограничения :

1 <= T <= 100

2 <= N <= 15

Первоначально перестановка не будет возрастающей последовательностью.

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

В приведенной выше задаче для перестановки длины 2 всегда побеждает игрок 1.

Для перестановки длины 3 игрок 2 выигрывает, если строка строго возрастает или убывает.

Для перестановки длины 4. Если игрок 1 может сделать строку строго возрастающей или убывающей, удалив символ, он выигрывает, в противном случае выигрывает игрок 2.

Отсюда вывод:

Если текущий игрок может сделать строку строго возрастающей, он выигрывает. (Тривиальный случай)

Если он/она может сделать это строго в убывающем порядке, то победитель определяется по количеству элементов в этой последовательности. Если в этой последовательности четное количество элементов, текущий игрок проигрывает, иначе выигрывает.

Но что делать, если результирующая строка не возрастает и не убывает??