← 返回题目列表

AtCoder · arc184_c

C. 山谷褶皱

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

我们有一张又长又薄的纸,其厚度可以忽略不计。我们执行以下操作 100 次:提起右端,将其折叠,使其与左端对齐,使用中心作为折痕。完成后 100 折叠,我们将纸张展开回原来的状态。此时,有 2^{100} - 1 纸张上的折痕,这些折痕可分为两种:山折和谷折。下图表示执行两次操作后的状态,其中红色实线表示山折,红色虚线表示谷折。

关于山谷褶皱
  • 如果折叠后纸张的背面在折痕处合在一起,则折痕就是山折。
  • 如果折叠后纸张的正面在折痕处合在一起,则折痕就是谷折。

image of folds

给你一个序列 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