문제

Just Odd Inventions 社は，「ただ奇妙な発明(just odd inventions)」をすることで知られている会社である．ここでは略してJOI 社と呼ぶ．

JOI 社は，看板商品である「長いだけのネクタイ」発売5 周年を記念し，新しく「長くなるだけのネクタイ」を開発した．この新型ネクタイの特徴は，その名の通り長さをいくらでも伸ばせることである．

JOI 社は，新型ネクタイの宣伝を目的とした披露会の開催を決定し，その司会にあなたを抜擢した．披露会ではまず，新型ネクタイを着用した何人かのモデルが舞台上に登壇する．最初，各モデルが着用しているネクタイの長さはすべて $1$ である．

その後，あなたはネクタイの長さを伸ばせる機能を観客に実感してもらうためのパフォーマンスを $N$ 回行う．各パフォーマンスは以下のように行われる．

1. まず，観客に好きな数を1 つ唱えてもらう．ここで観客が唱えた数を $x$ とおく．
2. 次に，司会のあなたはこれに反応するか無視するかを選ぶ．
   • 反応することを選んだ場合，あなたは登壇しているモデルのうち着用しているネクタイの長さが $x$ 以下であるような者を1 人選び，そのモデルのネクタイの長さを $x$ にする（着用しているネクタイの長さが元々 $x$ であるようなモデルも選ぶことができる点に注意せよ）．ただし，選ぶことのできるモデルが1 人も存在しない場合，披露会は失敗に終わる．
   • 無視することを選んだ場合，何もしない．

ただし，観客の唱えた数を2 回以上連続で無視してしまうと，観客が機嫌を損ね，披露会は失敗に終わる．

舞台上に登壇させるモデルの人数 $k$ ($k \ge 1$) はまだ決まっていないが，モデルを雇うのにはお金がかかるため， $k$ の値はできるだけ小さい方が望ましい．披露会が失敗に終わらないために必要なモデルの人数は各パフォーマンスで観客が唱える数に依存するが，あなたはその予知能力により， $i$ 回目 ($1 \le i \le N$) のパフォーマンスで観客が唱える数が $A_i$ であることを予見した．

披露会で観客が唱える数の情報が与えられたとき，披露会が失敗に終わらないために必要なモデルの人数 $k$ の最小値を求めるプログラムを作成せよ．

입력

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 ... A_N

출력

標準出力に，披露会が失敗に終わらないために必要なモデルの人数 $k$ の最小値を1 行で出力せよ．

제한

• $2 \le N \le 5\,000\,000$．
• $1 \le A_i \le 21$ ($1 \le i \le N$)．
• 入力される値はすべて整数である．

서브태스크

1. (10 점) $N \le 15$．
2. (6 점) $N \le 500$, $A_i \le 2$ ($1 \le i \le N$)．
3. (12 점) $N \le 500$, $A_i \le 5$ ($1 \le i \le N$)．
4. (18 점) $N \le 500$, $A_i \le 15$ ($1 \le i \le N$)．
5. (26 점) $N \le 500\,000$, $A_i \le 15$ ($1 \le i \le N$)．
6. (10 점) $N \le 500\,000$．
7. (18 점) 追加の制約はない．

예제 입력 1

5
5 3 4 2 1

예제 출력 1

2

$k = 2$ のとき，例えば以下のように披露会を行うことができる．

• まず，新型ネクタイを着用した2 人のモデルが舞台上に登壇する．最初，各モデルのネクタイの長さはいずれも $1$ である．
• 1 回目のパフォーマンスでは，観客は $5$ を唱える．あなたはこれを無視する．
• 2 回目のパフォーマンスでは，観客は $3$ を唱える．あなたはこれに反応して，1 人目のモデルを選び，そのネクタイの長さを $3$ にする．各モデルのネクタイの長さはそれぞれ $3, 1$ になる．
• 3 回目のパフォーマンスでは，観客は $4$ を唱える．あなたはこれに反応して，1 人目のモデルを選び，そのネクタイの長さを $4$ にする．各モデルのネクタイの長さはそれぞれ $4, 1$ になる．
• 4 回目のパフォーマンスでは，観客は $2$ を唱える．あなたはこれに反応して，2 人目のモデルを選び，そのネクタイの長さを $2$ にする．各モデルのネクタイの長さはそれぞれ $4, 2$ になる．
• 5 回目のパフォーマンスでは，観客は $1$ を唱える．あなたはこれを無視する．

$k = 1$ のとき，披露会は必ず失敗に終わる．よって，披露会が失敗に終わらないために必要なモデルの人数 $k$ の最小値は $2$ であるため， $2$ を出力する．

この入力例は小課題 1, 3, 4, 5, 6, 7 の制約を満たす．

예제 입력 2

6
2 1 1 2 2 1

예제 출력 2

1

$k = 1$ のとき，例えば以下のように披露会を行うことができる．

• まず，新型ネクタイを着用した1 人のモデルが舞台上に登壇する．最初，モデルのネクタイの長さは $1$ である．
• 1 回目のパフォーマンスでは，観客は $2$ を唱える．あなたはこれを無視する．
• 2 回目のパフォーマンスでは，観客は $1$ を唱える．あなたはこれに反応して，登壇している唯一のモデルを選び，そのネクタイの長さを $1$ にする．
• 3 回目のパフォーマンスでは，観客は $1$ を唱える．あなたはこれに反応して，登壇している唯一のモデルを選び，そのネクタイの長さを $1$ にする．
• 4 回目のパフォーマンスでは，観客は $2$ を唱える．あなたはこれに反応して，登壇している唯一のモデルを選び，そのネクタイの長さを $2$ にする．
• 5 回目のパフォーマンスでは，観客は $2$ を唱える．あなたはこれに反応して，登壇している唯一のモデルを選び，そのネクタイの長さを $2$ にする．
• 6 回目のパフォーマンスでは，観客は $1$ を唱える．あなたはこれを無視する．

なお，ネクタイの長さが変化しないようなモデルの選び方も許されていることに注意せよ．

よって，披露会が失敗に終わらないために必要なモデルの人数 $k$ の最小値は $1$ であるため， $1$ を出力する．

この入力例はすべての小課題の制約を満たす．

예제 입력 3

10
2 4 6 7 4 5 5 3 4 1

예제 출력 3

3

この入力例は小課題 1, 4, 5, 6, 7 の制約を満たす．