Alice 和 Bob 在一个排列上进行游戏,Alice 先手。
称一个长度为 n 的序列为一个排列,当且仅当 1,2,\dots,n 中的每个整数在序列中恰好出现一次。
初始给定一个长度为 n 的排列 a_1,a_2,\ldots,a_n。在游戏过程中的任意时刻,当前序列始终为一个长度为 m 的排列。双方轮流操作,每次必须选择下列两种操作之一:
- 选择一个满足 $ai>a{i+1} 的下标 i (1\le i<m),并交换 ai 和 a{i+1}$。
- 选择一个满足 a_{i+1}=a_i+1 的下标 i (1\le i
,并删除 $ai 和 a{i+1},随后将剩余元素按照相对大小重新编号:其中第 k 小的元素被重新编号为 k$,使得剩余序列重新成为一个排列。
例如,当前排列为 [2,3,4,1]。可以删除相邻的 2,3,剩余序列为 [4,1];重新编号后排列变为 [2,1]。
当一名玩家无法进行任何操作时,该玩家输掉游戏。假设 Alice 和 Bob 都采用最优策略,请判断最终获胜者。