分数: 900 点
问题陈述
我们有一张又长又薄的纸,其厚度可以忽略不计。我们执行以下操作 100 次:提起右端,将其折叠,使其与左端对齐,使用中心作为折痕。完成后 100 折叠,我们将纸张展开回原来的状态。此时,有 2^{100} - 1 纸张上的折痕,这些折痕可分为两种:山折和谷折。下图表示执行两次操作后的状态,其中红色实线表示山折,红色虚线表示谷折。
关于山谷褶皱
- 如果折叠后纸张的背面在折痕处合在一起,则折痕就是山折。
- 如果折叠后纸张的正面在折痕处合在一起,则折痕就是谷折。

给你一个序列 A = (A_1, A_2, \dots, A_N) of N 非负整数。在这里, 0 = A_1 < A_2 < \dots < A_N \leq 10^{18}.
对于每个整数 i 来自 1 通过 2^{100} - A_N - 1,定义 f(i) 如下:
- 数量 k = 1, 2, \dots, N 这样 (i + A_k)从左边算起第 3 条折痕是山折。
找出其中的最大值 f(1), f(2), \dots, f(2^{100} - A_N - 1).
约束
- 1 \leq N \leq 10^3
- 0 = A_1 < A_2 < \dots < A_N \leq 10^{18}
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
在一行中打印答案。
示例输入 1
4 0 1 2 3
示例输出 1
3
如果山和谷褶皱由 M 和 V分别有一个连续的折痕子序列,例如 MMVM。不存在像这样的连续子序列 MMMM,所以答案是 3.
示例输入 2
6 0 2 3 5 7 8
示例输出 2
4