E. 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:

对于所有数据，。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

For all test cases, .

Detailed constraints and hints are as follows (blank grids denote the same constraints as mentioned above):