[NOIP 2012 提高组] 开车旅行

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

有 $n$ 座从西向东编号为 $1$ 到 $n$ 的城市，第 $i$ 座城市海拔为 $h_i$，所有海拔互不相同。城市 $i,j$ 间的距离为 $|h_i-h_j|$。

小 A 和小 B 轮流开车，第一天由 A 驾驶，此后每天换人。他们从城市 $s$ 出发，只能向编号更大的城市前进，总行程不能超过 $x$。

• B 总是选择东方城市中距离最近的一座；
• A 总是选择东方城市中距离第二近的一座。

若距离相同，海拔较低的城市视为更近。若当前驾驶者没有符合规则的目的地，或到达目的地会让总里程超过 $x$，旅行立即结束。

请回答：

1. 对给定的 $x_0$，选择一个起点，使 A 的总里程与 B 的总里程之比最小。若 B 的总里程为 $0$，比值视为无穷大；多个起点比值相同时，选择海拔最高者。
2. 对每组起点 $s_i$ 和里程上限 $x_i$，求 A、B 各自的总里程。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个互不相同的整数 $h_1,h_2,\ldots,h_n$。

第三行一个整数 $x_0$。

第四行一个整数 $m$，表示询问数。

接下来 $m$ 行，每行两个整数 $s_i,x_i$。

输出格式

共输出 $m+1$ 行。

第一行输出最优起点 $s_0$。

接下来 $m$ 行，每行输出两个整数，依次为对应旅行中 A 和 B 的总里程。

样例输入 1

4
2 3 1 4
3
4
1 3
2 3
3 3
4 3

样例输出 1

1
1 1
2 0
0 0
0 0

样例输入 2

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

样例输出 2

2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

样例说明

样例 1 的城市与距离关系如下图。

数据范围

对于所有数据：$1\le n,m\le10^5$，$-10^9\le h_i\le10^9$，$1\le s_i\le n$，$0\le x_0,x_i\le10^9$，且所有 $h_i$ 互不相同。

本题采用独立计分点，各子任务内所有测试点等分。