该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

噜噜的是个收集怪

题目背景

噜噜是一位非常喜欢收集糖果的小朋友。他有 $N$ 堆糖果，排成一排，从左到右依次编号为 $1, 2, \ldots, N$。每一堆初始时都有一定数量的糖果。

有一天，一只调皮的小羊出现了。这只小羊非常喜欢吃糖果，而且它有一个特殊的习惯：它会进行 $K$ 次操作，每次操作它会选择一个区间 $[L, R]$（表示从第 $L$ 堆到第 $R$ 堆，包含 $L$ 和 $R$），然后从这个区间里的每一堆糖果中都拿走一颗糖果。如果某一堆糖果在小羊来拿的时候已经没有糖果了（即糖果数量为0），那么小羊在那一堆就什么也拿不到，该堆糖果数量仍然为0。

现在，噜噜想知道，在小羊进行了 $K$ 次操作之后，所有糖果堆中，剩余糖果数量最少的是哪一堆？以及那一堆剩下了多少颗糖果？如果有多堆糖果数量一样少，请输出其中糖果堆编号最小的那个。

问题描述

给定 $N$ 堆糖果的初始数量，以及小羊的 $K$ 次操作。每次操作给定一个区间 $[L, R]$。对于每次操作，你需要将编号从 $L$ 到 $R$ 的每一堆糖果的数量减 1（但不能减到负数，最少为0）。

所有操作完成后，找出剩余糖果数量最少的糖果堆。如果有多堆糖果数量并列最少，则选择编号最小的那一堆。输出这一堆的编号和它剩余的糖果数量。

输入格式

第一行包含一个整数 $N$，表示糖果堆的数量。 第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$，表示每堆糖果的初始数量。 第三行包含一个整数 $K$，表示小羊操作的次数。 接下来 $K$ 行，每行包含两个整数 $L$ 和 $R$，描述一次操作的区间。注意，$L$ 和 $R$ 是1-indexed的。

输出格式

输出一行，包含两个整数，用空格隔开。第一个整数是最少糖果堆的编号（1-indexed），第二个整数是该堆剩余的糖果数量。

样例输入与输出

样例输入 1

5
10 8 12 6 9
3
1 3
2 4
4 5

样例输出 1

4 4

样例解释 1

初始糖果: [10, 8, 12, 6, 9] 操作 1 (1, 3): 小羊从第1、2、3堆各拿走1颗糖。 糖果变为: [9, 7, 11, 6, 9]

操作 2 (2, 4): 小羊从第2、3、4堆各拿走1颗糖。 糖果变为: [9, 6, 10, 5, 9]

操作 3 (4, 5): 小羊从第4、5堆各拿走1颗糖。 糖果变为: [9, 6, 10, 4, 8]

最终糖果: [9, 6, 10, 4, 8] 第1堆: 9颗 第2堆: 6颗 第3堆: 10颗 第4堆: 4颗 第5堆: 8颗 最少的是第4堆，有4颗糖果。所以输出 4 4。

数据规模与约定

对于所有测试数据，保证：

• $1 \le N \le 2000$
• $0 \le K \le 2000$
• $0 \le a_i \le 10^9$ (初始糖果数量)
• $1 \le L \le R \le N$ (操作区间)

子任务：

• 子任务 1 (10分): $N \le 10$, $K \le 10$, $a_i \le 100$。
• 子任务 2 (20分): $N \le 100$, $K \le 1000$, $a_i \le 1000$。
• 子任务 3 (20分): $N \le 1000$, $K \le 100$, $a_i \le 1000$。
• 子任务 4 (50分): 无特殊限制，即符合整体数据规模 $N \le 2000, K \le 2000, a_i \le 10^9$。