题目描述

一个水龙头正在向一个细长的水族箱中注水，水族箱内有若干垂直隔板（挡板）。水族箱初始为空，且底部完全水平。问需要多长时间水才会从最左侧或最右侧的隔板溢出？

• 水龙头位于 $x=0$ 位置上方
• 隔板位置：左侧位于 $x=-1, -3, -5, \ldots, \text{leftx}$；右侧位于 $x=1, 3, 5, \ldots, \text{rightx}$
• 隔板垂直于地板和水族箱侧壁，高度各不相同
• 水族箱长度大于 $\text{rightx}-\text{leftx}$，侧壁高度高于最高隔板，宽度恒为 $1$ 单位
• 注水速率：$1$ 立方单位/秒
• 假设水为理想液体：始终向下流动，若无法向下流动则向所有水平方向均匀扩散

输入格式

每个测试用例包含两个整数 $\text{leftx}$（奇数 $\leq -1$）和 $\text{rightx}$（奇数 $\geq 1$）。随后若干行按从左到右顺序给出每个隔板的高度（正整数）。每个测试用例不超过 $1000$ 个隔板。输入以一行 $0\ 0$ 结束。

输出格式

对于每个测试用例，输出一个整数，表示水从最左或最右隔板溢出所需的时间（秒）。

输入样例 1

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

输出样例 1

6
6
8