题目内容

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

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

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

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

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

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

对于左侧同理。