题目描述

给定一个长度为 $n$ 的序列，给定 $m$ 次查询，每次查询一个区间，求这个区间从 $r$ 开始到 $l$ 每次最小值产生变化的结果。

输入格式

第一行一个整数 $n$ 表示序列长度。

第二行 $n$ 个正整数表示初始序列。 接下来一行一个正整数 $m$ 表示询问的次数。

下面 $m$ 行，每行两个数字 $l,r$ 表示询问的区间。

输出格式

对于 $m$ 次询问，输出每次询问的结果。

样例 1 输入

8
1 2 3 1 2 9 10 20
4
1 3
1 4
1 6 
1 8

样例 1 输出

1 2 3
1 
1 2 9
1 2 9 10 20

数据范围

$n,m\leq 10^5$