# #554. 「LibreOJ Round #8」MIN&MAX II

#### 题目描述

• ，且不存在 满足
• ，且不存在 满足
• ，且不存在 满足
• ，且不存在 满足

（形式化地，对于一对 ，求所有满足 中， 的最大值 ，以及满足 组数 。）

For an -order permutation , we set up an undirected simple graph with vertices numbered from to . We create an edge between each vertice and the nearest vertices in each side which correspond a greater (or less) value than .
Formally,in this graph, , the edge exists iff at least one of the following four conditions hold:

• , and no exists such that ;
• , and no exists such that ;
• , and no exists such that ;
• , and no exists such that .

For a segment , define its corresponding permutation as an -order permutation with the same relative orders of elements as ; that is, for all , the boolean value is the same as the boolean value .
For instance, for the permutation , is a permutation of length with the same relative orders of elements as , i.e. .

The chromatic number of an undirected graph is the smallest number of colors needed to give each vertex a color such that every edge connects two vertices with different colors. We call this .

Given a permutation of length , please find the chromatic number of .
Additionally, please answer queries in the form of asking for: the greatest chromatic number among those of all corresponding permutations of each subsegment of , ; and the number of subsegment that achieve this maximum number .
(Formally,for each given ,,calculate the maximum possible value of ,called ,and .)

#### 输入格式

The first line contains a positive integer .

The second line contains positive integers .

The third line contains an integer .

The following lines each contains two positive integers , denoting a query.

#### 输出格式

Output contains lines in total. The first one should contain a positive integer denoting the chromatic number of , followed by lines each containing two integers for each query.

#### 样例输入

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


#### 样例输出

4
4 1
2 3
3 3
3 6
1 1


#### Sample Input

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


#### Sample Output

4
4 1
2 3
3 3
3 6
1 1


#### Sample Explanation

The following picture describes and a way of coloring: