题目描述

你的朋友达达被邀请参加一个叫做“超级备忘录”的电视节目。

在这个节目中，参与者需要玩一个记忆游戏。

在一开始，主持人会告诉所有参与者一个数列，$A_1, A_2, \dots, A_n$。

接下来，主持人会在数列上做一些操作，操作包括以下几种：

1. ADD x y D：给子序列 $\{A_x, \dots, A_y\}$ 统一加上一个数 $D$。
2. REVERSE x y：将子序列 $\{A_x, \dots, A_y\}$ 逆序排布。
3. REVOLVE x y T：将子序列 $\{A_x, \dots, A_y\}$ 轮换 $T$ 次。
4. INSERT x P：在 $A_x$ 后面插入 $P$。
5. DELETE x：删除 $A_x$。
6. MIN x y：询问子序列 $\{A_x, \dots, A_y\}$ 中的最小值。

为了使得节目更加好看，每个参赛人都有机会在觉得困难时打电话请求场外观众的帮助。

你的任务是看这个电视节目，然后写一个程序对于每一个询问计算出结果，这样可以使得达达在任何时候打电话求助你的时候，你都可以给出正确答案。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行给出了序列中的数。

接下来一行包含一个整数 $M$，描述操作和询问的数量。

接下来 $M$ 行给出了所有的操作和询问。

输出格式

对于每一个 MIN 询问，输出正确答案。

每个答案占一行。

样例

5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5

5

样例解释

初始序列

$n = 5$
序列：$[1, 2, 3, 4, 5]$

操作 1：ADD 2 4 1

给子序列 $[A_2, A_3, A_4]$ 即 $[2, 3, 4]$ 加 $1$，变为 $[3, 4, 5]$。
新序列：$[1, 3, 4, 5, 5]$

操作 2：MIN 4 5

查询子序列 $[A_4, A_5]$ 即 $[5, 5]$ 的最小值，结果为 $5$。

数据范围

• $n \le 100000$
• $M \le 100000$
• 初始序列中数的范围 $[1, 10^5]$
• 操作保证合法，序列中的数始终都在 int 范围内。

操作详解

假设序列下标从 $1$ 开始。

1. ADD x y D
   将区间 $[x, y]$ 的所有元素加 $D$。

2. REVERSE x y
   将区间 $[x, y]$ 的元素逆序。

3. REVOLVE x y T
   将区间 $[x, y]$ 循环右移 $T$ 次。
   注意：$T$ 可能很大，但区间长度为 $len = y - x + 1$，实际有效轮换次数为 $T \bmod len$。

4. INSERT x P
   在位置 $x$ 之后插入 $P$。即新元素 $P$ 的下标为 $x+1$，原序列中下标大于 $x$ 的元素后移一位。

5. DELETE x
   删除位置 $x$ 的元素，后续元素前移。

6. MIN x y
   查询区间 $[x, y]$ 的最小值。

算法提示

由于 $n$ 和 $M$ 都达到 $10^5$，且涉及区间操作、插入删除，需要使用高效的数据结构。
平衡树（如 Splay 或 Treap）或 块状链表 可以支持这些操作：

• 区间加：打懒标记
• 区间翻转：打翻转标记
• 区间循环移动：可通过三次翻转实现，或直接切割合并
• 插入删除：平衡树基本操作
• 区间最小值：维护子树最小值

注意：REVOLVE 操作可以转化为：将区间 $[x, y]$ 分为 $[x, y-T']$ 和 $[y-T'+1, y]$ 两部分（其中 $T' = T \bmod len$），然后交换这两部分。可以通过切割合并实现。

复杂度要求

• 每次操作时间复杂度应为 $O(\log n)$ 或 $O(\sqrt{n})$，才能通过全部数据。