#44 star

Statement

규진이는 $N$ 개의 별을 순서대로 관측하려고 한다. $i$ 번째로 관측할 별의 밝기는 $A_i$ 이다.

규진이는 반드시 관측 순서에 따라 별을 정확히 한 번씩 관찰해야 하고, 하루에 여러 개의 별을 관측할 수 있다. 또한, 하루 동안 관측한 별의 밝기 중 최댓값과 최솟값의 차이는 그날 관측한 별의 수 이하여야 한다.

규진이가 위 조건을 모두 만족하면서 모든 별을 관측하기 위해 필요한 최소 일수 $d$ 를 구해주자.

첫째 줄에 관측한 별의 개수 $N$ 이 주어진다. $(1 \le N \le 200\, 000)$

둘째 줄에 각 별의 밝기 $A_1, A_2, \ldots , A_N$ 이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$

모든 별을 관측하기 위해 필요한 최소 일수를 출력한다.

Sample 1

Input

6
2 4 1 5 8 5

Output

2

Sample 2

Input

10
5 9 12 6 4 1 2 7 2 4

Output

4