题目描述

男孩 Egor 一直在玩一款流行游戏 “TOTA”。游戏中有 $n$ 种英雄。

一个长度为 $k$ 的英雄队列定义为一个英雄类型序列

如果长度为 $k$ 的队列中，类型 $1$ 到 $k$ 的每一种英雄都恰好出现一次，那么 Egor 称这个队列是“糟糕的”。换句话说，一个长度为 $k$ 的队列对 Egor 来说是糟糕的，当且仅当对于每个 $1\le i\le k$，都存在一个位置 $j$ 使得 $b_j=i$。

Egor 有游戏成瘾问题，因此每天都和朋友 Timofey 一起玩这款游戏。由于游戏仍在开发中，每天可用于构造队列的英雄序列相同，长度为 $n$，其中第 $i$ 个英雄的类型为 $a_i$。

Timofey 会和 Egor 玩 $q$ 天。每天会固定一个数 $l_i$，表示队列中第一个英雄的下标。因此在第 $i$ 天，Timofey 可以选择任意 $r_i$（$l_i\le r_i\le n$），并使用下标为

的连续英雄构成队列。

Timofey 希望 Egor 不再一直玩 “TOTA”，而是专心学习。为此，Timofey 想用一个糟糕队列夺走 Egor 的全部快乐。第 $i$ 天，Egor 的快乐值为 $x_i$。如果当天摆出的糟糕队列长度至少为 $x_i$，Egor 就会失去全部快乐。

Timofey 想尽可能经常地夺走 Egor 的快乐。因此对于每一天 $i$，他想知道：

1. 能夺走 Egor 快乐的糟糕队列的最小长度是多少；
2. 当天有多少种队列构造能够夺走 Egor 的快乐。

由于经常玩 “TOTA”，Timofey 的认知能力已经下降，所以他需要你的帮助。

输入格式

第一行包含一个整数 $g$（$0\le g\le 8$），表示当前测试点所属分组编号。

第二行包含两个整数 $n,q$（$1\le n,q\le 10^6$），分别表示英雄数量和天数。

第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$），表示初始英雄序列中的英雄类型。

接下来 $q$ 行，每行包含两个整数 $l_i,x_i$（$1\le l_i\le n$，$1\le x_i\le n-l_i+1$），表示第 $i$ 天队列起点和 Egor 的快乐值。

输出格式

输出 $q$ 行。第 $i$ 行输出第 $i$ 天的答案：能夺走快乐的糟糕队列的最小长度，以及能夺走快乐的糟糕队列数量。

如果第 $i$ 天不存在能够夺走快乐的队列，输出：

-1 0

样例 1

0
6 3
1 4 2 3 1 4
1 1
2 1
3 1

1 2
4 1
3 2

样例 2

0
3 1
3 3 1
1 1

-1 0

样例解释

考虑第一个样例。

第一天，Egor 的快乐值为 $x_1=1$，因此只需要长度至少为 $1$ 的糟糕队列即可夺走他的快乐。从 $l_1=1$ 开始，有两个糟糕队列：

• 1
• 1, 4, 2, 3

最小长度为 $1$，数量为 $2$。

第二天，起点为 $l_2=2$，此时只有一个糟糕队列：4, 2, 3, 1。注意，队列 4, 2, 3, 1, 4 不是糟糕队列，因为英雄类型 $4$ 出现了两次。

第三天，从第 $3$ 个英雄开始，可以得到两个糟糕队列：

• 2, 3, 1
• 2, 3, 1, 4

评分方式

本题测试点由 8 个分组组成。只有通过某一组及其要求的部分前置分组时，才能获得该组分数。注意，部分分组不要求通过样例。Offline-testing 表示该组测试结果只会在比赛结束后给出。