/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
厚さを無視できる細長い紙があります。右端を持ち上げ、中央を折り目にして左端に合わせて折りたたむ操作を 100 回行い、もとに戻します。このとき紙には折り目が 2^{100} - 1 個あり、これらは山折り、谷折りの 2 種類に分類できます。下の図は 2 回操作を行った状態を表した図で、赤い実線は山折り、赤い点線は谷折りを表します。
山折り、谷折りとは
- ある折り目が山折りであるとは、折り目が紙の裏面同士が重なる方向に折られたことをいいます。
- ある折り目が谷折りであるとは、折り目が紙の表面同士が重なる方向に折られたことをいいます。
長さ N の非負整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。ここで 0 = A_1 < A_2 < \dots < A_N \leq 10^{18} です。
1 以上 2^{100} - A_N - 1 以下の整数 i に対し、 f(i) を以下のように定義します。
- k = 1, 2, \dots ,N のうち、左から i + A_k 番目の折り目が山折りであるものの個数
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 行に出力せよ。
入力例 1
4 0 1 2 3
出力例 1
3
山折り、谷折りをそれぞれ M, V と表すことにすると、折り目には MMVM と連続する箇所が存在します。MMMM と連続する箇所は存在しないので、答えは 3 となります。
入力例 2
6 0 2 3 5 7 8
出力例 2
4
Score : 900 points
Problem Statement
We have a long, thin piece of paper whose thickness can be ignored. We perform the following operation 100 times: lift the right end, fold it so that it aligns with the left end using the center as a crease. After completing the 100 folds, we unfold the paper back to its original state. At this point, there are 2^{100} - 1 creases on the paper, and these creases can be classified into two types: mountain folds and valley folds. The figure below represents the state after performing the operation twice, where red solid lines represent mountain folds and red dashed lines represent valley folds.
About mountain and valley folds
- A crease is a mountain fold if it is folded so that the back sides of the paper come together at the crease.
- A crease is a valley fold if it is folded so that the front sides of the paper come together at the crease.
You are given a sequence A = (A_1, A_2, \dots, A_N) of N non-negative integers. Here, 0 = A_1 < A_2 < \dots < A_N \leq 10^{18}.
For each integer i from 1 through 2^{100} - A_N - 1, define f(i) as follows:
- The number of k = 1, 2, \dots, N such that the (i + A_k)-th crease from the left is a mountain fold.
Find the maximum value among f(1), f(2), \dots, f(2^{100} - A_N - 1).
Constraints
- 1 \leq N \leq 10^3
- 0 = A_1 < A_2 < \dots < A_N \leq 10^{18}
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer in one line.
Sample Input 1
4 0 1 2 3
Sample Output 1
3
If mountain and valley folds are represented by M and V, respectively, there is a contiguous subsequence of creases like MMVM. There is no contiguous subsequence like MMMM, so the answer is 3.
Sample Input 2
6 0 2 3 5 7 8
Sample Output 2
4