B. 数列递推

sosusosu 虐爆 OI 之后成为了一名文化课选手。一天，他做作业碰到了一堆数列问题，每道题给出的数列都是以下形式：

sosusosu 研究了这些数列，发现它们十分优美充满人类智慧，于是决定出一道 OI 题。

sosusosu 给了你一个集合 ，他想问你对于 中的每个数 ，使得 最大的 和使得 最小的 分别是多少。如果这样的 有多个，请你回答最小的一个。

另外，sosusosu 准备对他作业中碰到的每个数列都让你回答一次，不过每次的集合 是一样的。

输入第一行一个整数 表示 中元素个数。
第二行 个整数 表示 中的元素。保证它们是非负整数且严格递增（即 ）。
第三行一个整数 表示询问的数列个数。
接下来 行每行三个整数 描述一个数列。

输出共 行，每行依次输出两个整数 ，依次表示 的元素 中，使得 最大的 和使得 最小的 的值。如果这样的 有多个，请你回答最小的一个。

样例输入 1

8
1 2 3 4 5 6 7 8
2
10 -6 1
0 0 1

样例输出 1

2 1
1 1

样例解释 1

第一个数列的前 项分别为 ，使得 最大的 为 和 （）其中 较小，使得 最小的 为 （）。
第二个数列每项都等于 ，因此 中的每个元素 都既使 最大也使 最小，故答案是 中最小元素。

样例输入 2

3
0 1 2
2
-2 3 1
3 -2 2

样例输出 2

1 0
0 1

样例解释 2

第一个数列的前 项分别为 ，使得 最大的 为 （），使得 最小的 为 （）。
第二个数列的前 项分别为 ，使得 最大的 为 （），使得 最小的 为 （）。

样例输入 3

29
2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912
4
10000000 10000000 100
9999984 -6180330 1
9999984 -6180329 1
-10000000 4142135 2

样例输出 3

536870912 2
2 536870912
536870912 16
8 536870912

更多样例

见附加文件（在页面上方下载）。其中除了前 3 个样例外还有约定分别和测试点 1, 9, 14 相同的样例各一个。

对于所有数据，，，，，，保证 严格单调递增。

注意，本题输入规模较大，请使用较快的方式读入。LOJ 上 C 语言的 scanf、C++ 的关闭同步的 cin、Pascal 的 read 读入此题数据时间均在 50 ~ 200 毫秒之间。

所有测试数据的范围和特点如下表所示：
（未标明的以上述所有数据的限制为准）