AT_joisc2016_h 回転寿司

给出一个有 $N$ 个点的环，环上各点有一个初始权值 $a_i$。 给出 $Q$ 个询问，每次询问给出一个区间 $[S_i,T_i]$ 和一个值 $A_i$，对于 $A_i$ 的变动定义如下（$S_i$ 可能会小于 $T_i$ 因为是**环形**）： ```cpp for (int i=Si;i!=Ti%n+1;i=i%n+1) if(a[i]>Ai) swap(a[i],Ai); ``` 对于每个询问，回答遍历完区间 $[S_i,T_i]$ 后 $A_i$ 的最终值。 注：我们按逆时针方向在环上编号，并规定 $[S_i,T_i]$ 为从位置编号为 $S_i$ 的点逆时针遍历至位置编号为 $T_i$ 的点所经过点的集合。

第一行包括两个数 $N$ 与 $Q$ 表示环的大小和询问的个数。 之后的 $N$ 行每行共一个整数，第 $i$ 个为 $a_i$。 之后的 $Q$ 行每行共三个整数 $S_i,T_i,A_i$，表示如上所示。

输出包括 $Q$ 行，每行包括一个数，为变动结束后 $A_i$ 的值。

对于全部的数据，$1\leq N\leq 4\times 10^5$，$1\leq Q\leq 25000$，$1\leq a_i\leq 10^9$，$1\leq S_i,T_i\leq N$，$1\leq A_i\leq 10^9$。 子任务 1（5 分）：$N\leq 2000$，$Q\leq 2000$。 子任务 2（15 分）：$S_i=1$，$T_i=N$（$1\leq i\leq N$）。 子任务 3（80 分）：无额外限制。