题目描述

使用ST算法求解数组区间内的最大值为多少

输入格式

首先一行输入一个数字n，接着第二行输入n个数组元素，第三行输入需要查询的区间数q，接下来的q行输入q个区间。

输出格式

输出不同的区间中最大值

样例

输入样例 1

5
3 3 3 3 3
3
1 5
2 4
3 3

输出样例 1

区间[1,5]的最大值为: 3
区间[2,4]的最大值为: 3
区间[3,3]的最大值为: 3

输入样例 2

1
5
1
1 1

输出样例 2

区间[1,1]的最大值为: 5

输入样例 3

6
1 2 3 4 5 6
2
1 6
3 5

输出样例 3

区间[1,6]的最大值为: 6
区间[3,5]的最大值为: 5