思路：单调栈+ST表/线段树

显然，对于先手仅能选取$[l,r]$中最大的数，因此我们需要知道该区间的最大值，可以用ST表/线段树等数据结构进行预处理，同时我们处理出最大值所在的位置，额外用数组记录即可。

而对于后手，要求$[L,R]$最小且要赢，说明要找到两边区间内大于$[l,r]$中最大值且距离最近的位置。可以使用单调栈来预处理。

对于$a_i$右边的最大值，我们维护一个单调递减栈，从左往右枚举，当栈头出栈时，当前数即为栈头右侧第一个比它大的数的位置，记录即可。

对于左侧同理。

题目内容

小明和小美在玩一个游戏，游戏中有一个长度为$n$的数组$a$,她们会玩$q$轮游戏，每轮游戏都是独立的。

游戏规则如下，双方都会执行最优策略：

$1)$第一步，游戏给出一个区间[$l,r$]。

$2)$第二步，小明在[$l,r$]区间中选择一个数。

$3)$第三步，小美将区间扩展成[$L,R$] ([$L,R$]必须包含[$l,r$])，然后在[$L,R$]区间中选择一个数，但不能跟小明选同一个数。

$4)$第四步，小明和小美选择的数字较大的一方获胜，若相同则平局。

小美想知道她每一轮的输赢状态，并且她想知道要达到输赢状态所需的[$L,R$]区间长度最小是多少。

输入描述

第一行输入两个正整数$n$，$q$($2≤n,q≤2×10^5$),表示数组长度和询问次数。

第二行输入$n$个正整数$a$($1≤a_i≤10^9$),表示数组。

接下来$q$行，每行输入两个整数($1≤l≤r≤n$)，表示询问

输出描述

对于每个询问先输出一行，若小美可以获胜则输出”$win$“,若平局则输出”$draw$“,多失败则输出”$lose$“。

第二行输出达到最终状态所需的区间长度的最小值。

样例1

输入

6 2
1 1 4 5 1 4
1 3
4 4

输出

win
4
lose
2

说明

第$1$个询问，小明会选择数字$4$，小美将区间扩展成[$1,4$]，选择数字$5$，小美获胜，扩展后的区间长度为$4$。

第$2$个询问，小明会选择数字$5$，小美将区间扩展成[$3,4$]，选择数字$4$，小美获胜，扩展后的区间长度为$2$。