Just dropped an apple

difficulty: ★★☆☆☆☆

Problem Description

To stave off boredom, Yoji started imagining that apples have just fallen high from the sky. A $k$-th apple takes exactly $k-1$ distance to an arbitrary direction from one of existing.

Nearby, there are $N$ number of parrots with an $X$ coordinate for each. To hit all the parrots, what is the minimum number of apples that he needs to summon?

Constraints

• $1 \leq N \leq 2000$
• $-10^8 \leq X_i \leq 10^8$
• $i \neq j \to X_i \neq X_j$

Input style

N
X_1 X_2 ... X_N

Input example 1

4
4 6 3 7

Output example 1

4

This is feasible by following the steps below.

1. Drop at $3$
2. Drop at $4$ from $3$
3. Drop at $6$ from $4$
4. Drop at $7$ from $4$.

Input example 2

2
1 16

Output example 2

6

At times, it's inevitable to sacrifice some apples to reach a far target.

Input example 3

1
100000000

Output example 3

1

Hit one, and that's it!