#524. 「LibreOJ β Round #4」游戏

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: qmqmqm

题目描述

qmqmqm和sublinekelzrip要进行一场游戏,其规则是这样的:

首先有一个序列,其中每个位置是一个整数或是X。双方轮流将X的位置填入不在序列中的实数,直到序列中充满数字为止。qmqmqm优先填数。若最后这个序列的逆序对数目为奇数,则qmqmqm获得胜利,否则sublinekelzrip获得胜利。qmqmqm想知道若双方均采取最优决策,在一个给定的序列下他能否获胜。

注意虽然起始序列中只有整数,但可以填入非整数的实数。

输入格式

第一行包含一个正整数nn,表示序列的长度。

之后nn行,每行或为一个整数aia_i,或为一个字符X。

输出格式

输出仅包含一个字符,若qmqmqm获胜,输出"W",否则输出"L"。

样例

样例输入1

2
X
X

样例输出1

L

样例解释1

若qmqmqm在第一个位置填入 aa,则sublinekelzrip只要在后一个位置填入 a+1a+1

若qmqmqm在第二个位置填入 bb,则sublinekelzrip只要在后一个位置填入 b1b-1

样例输入2

2
X
57

样例输出2

W

样例解释2

qmqmqm在第一个位置填入 7171 即可获胜。

数据范围与提示

1n1000001 \leq n \leq 100000

109ai109-10^9 \leq a_i \leq 10^9

iji \neq j,则aiaja_i \neq a_j