题目描述

地图上画出了一段地壳的地形，它是一条折线。在这条折线上，按相等间距标出了 $N$ 个点，从左到右依次编号为 $1$ 到 $N$。

原题面在此处给出了一个包含 $14$ 个点的示意图，用来说明峰、谷与内部点的定义。

每个点 $i$ 具有一个整数高度 $h_i$。只有部分点的高度已知。一个合法地形总满足：

$$h_1 < h_2$$ $$h_i \ne h_{i+1} \quad (1 \le i < N)$$

对所有满足 $1 < i < N$ 的点 $i$：

• 若 $h_{i-1} < h_i > h_{i+1}$，则点 $i$ 是一个峰；
• 若 $h_{i-1} > h_i < h_{i+1}$，则点 $i$ 是一个谷；
• 否则点 $i$ 称为内部点。

点 $1$ 一定是谷；点 $N$：

• 若 $h_{N-1} < h_N$，则它是峰；
• 若 $h_{N-1} > h_N$，则它是谷。

在原题面的示意图中，点 $2, 7, 11$ 是峰，点 $1, 4, 9, 14$ 是谷，其余点为内部点。

给定峰和谷的总数 $T$，以及这些点的编号序列 $a$（严格递增）。例如在示意图中：

$$T = 7$$ $$a = \{1, 2, 4, 7, 9, 11, 14\}$$

定义地形的高差为：该地形中最高点与最低点的高度差。

请编写程序 relef，求出以下两个值：

1. 在不改变已知高度的前提下，合法地形可能的最小高差；
2. 在所有高差最小的合法地形中，所有峰与谷的高度和的最小值。

若一个解仅正确求出了第一个值，则该子任务只能得到一半分数。

输入格式

第一行输入整数 $T$，表示峰与谷的个数。
第二行输入长度为 $T$ 的序列 $a$，表示这些峰与谷点的编号，且按升序给出。保证：

$$a_1 = 1, \quad a_T = N$$

第三行输入整数 $W$，表示已知高度的点的个数。
接下来 $W$ 行，每行两个整数 $k_i, h_i$，分别表示点的编号以及它的高度，满足：

$$k_i < k_{i+1}$$

点 $k_i$ 可能是内部点、峰或谷。

输出格式

输出一行两个正整数：

• 条件 (1) 中的最小高差；
• 条件 (2) 中要求的最小高度和。

数据范围

$$2 \le T \le 3 \times 10^5$$ $$1 \le W \le 3 \times 10^5$$ $$W \le N$$ $$1 = a_1 < a_2 < \cdots < a_T = N \le 3 \times 10^5$$$$|h_i| \le 10^9$$

说明 1： $|h_i|$ 的限制只针对输入中已知的高度；未知点的高度可以是任意整数。
说明 2： $|x| = x$ 当 $x \ge 0$；$|x| = -x$ 当 $x < 0$。

子任务

若某个子任务中仅第一问全部正确，则该子任务得分为该子任务分值的 $50\%$。

| 子任务 | 分值 | $N \le$ | $|h_i| \le$ | 额外限制 | | ------ | ---: | --------------: | ----------: | -------- | | 1 | 10 | 10 | 10 | 无 | | 2 | 12 | 500 | 100 | 无 | | 3 | 18 | 500 | $10^9$ | 无 | | 4 | 22 | $3 \times 10^5$ | $10^9$ | $W = 1$ | | 5 | 38 | $3 \times 10^5$ | $10^9$ | 无 |

样例 1

输入 1

7
1 2 4 7 9 11 14
1
6 5

输出 1

3 29

样例 2

输入 2

2
1 10
2
1 -5
5 5

输出 2

15 5

样例解释 1

第一个样例就是题面中的那张示意图。图中用黑色标出峰和谷点的编号，用蓝色标出高度，用红色标出已知高度的第 $6$ 号点。

在一种最优构造中，所有点的高度都位于某两个整数高度之间，因此最小高差为 $3$。在所有高差为 $3$ 的合法构造中，所有峰和谷的高度和的最小值为 $29$。