【题目背景】

随机数据生成依赖 srand(time(0))。

两岁那年，$\text{X}$ 阿克就在 $\text{XSP}{-}\text{S}$ 中获得了 $632$ 分的高分。

三岁那年，$\text{X}$ 阿克在 $\text{XOI}$ 中摘得桂冠。由于太神仙了，牠获得了 $498$ 分的好成绩。

四岁那年，$\text{X}$ 阿克就代表 $\text{X}$ 国参加 $\text{IXI}$ 并且 $1.32s$ 轻松阿克。

五岁那年，$\text{X}$ 阿克已斩获 $435$ 块金牌，成为获得金牌数量最多的 $G$ 尼斯记录保持者。

六岁那年，$\text{X}$ 阿克进入 $\text{X}$ 国国家重点科学研究院计算机与电子技术系，成为该系年龄最小的首席研究员。

七岁那年，$\text{X}$ 阿克自学了物理、化学、数学、生物、天文、体育、美术、音乐、地理、殡葬、管理、金融、会计、美食品鉴、平面设计、土木工程、错觉摄影等一系列竞赛常见项目并轻松蝉联第一。

八岁那年，$\text{X}$ 阿克凭借其 $4.55319\times10^{17}$ 的视力的三眼，捕捉到了 $1.43589\times10^{224}$ 光年外的适宜海嗣生存的星球上的未知生物（？），海嗣欢呼雀跃。

九岁那年，$\text{X}$ 阿克已经在全球的各大高等教育机构作了不下 $10^{137}$ 场成功学讲座。

十岁那年，$\text{X}$ 阿克已经在全海嗣心目中树立起了高大形象。

十一岁那年，$\text{X}$ 阿克使 $\text{X}$ 国实现了究极至尊豪华无上主义。

十二岁那年，$\text{X}$ 阿克身价突破 $1.14\times10^{191}$ 龙门币。

十三岁那年，$\text{X}$ 阿克成为了海嗣 $\text{win}$。

$\text{X}$ 阿克今年十四岁了，牠度过了一个相对成功的海嗣生。

【题目描述】

$\text{X}$ 阿克给了你一个长度为 $n$ 的数组 $a$，保证 $1\le a_i\le n\space(1\le i\le n)$。

$\text{X}$ 阿克递归地定义了参数和返回值都是一个二元组的函数 $f^k((l,r))$：

$$ \left\{\begin{matrix}f^1((l,r))=(\min\limits_{i=l}^r\space a_i,\max\limits_{i=l}^r\space a_i)\\f^k((l,r))=f^1(f^{k-1}(l,r))\end{matrix}\right. $$

$\text{X}$ 阿克想找到最小的 $k$ 使得 $f^k((l,r))=(1,n)$。

$\text{X}$ 阿克现在有 $q$ 次询问，每一次询问给出 $l$、$r$，请你给出最小的 $k$。若无解，则输出 $\texttt{qwq}$。

【输入格式】

第一行一个正整数 $n$。

第二行一行共 $n$ 个空格分隔的正整数 $a_1,a_2,\cdots,a_n$。

第三行一个正整数 $q$。

接下来 $q$ 行每行两个正整数 $l$、$r$ 表示一次询问。

【输出格式】

$q$ 行，每行一个正整数或字符串 $\texttt{qwq}$，表示答案。

【输入输出样例】

样例输入 #1

2
1 2
2
1 2
1 1

样例输出 #1

0
qwq

【数据范围】

注意：本题采用捆绑测试，只有当你通过一个子任务中的所有测试点后，你才能拿到这个子任务的分数。

对于 $100\%$ 的数据，满足 $1\le a_i\le n,q\le10^5$。