Description

A sharpshooter wants to shoot down $n$ balloons, and each balloon has a height, denoted by $h_i$.

Because of the balloons’ elasticity, an arrow will drop. After hitting a balloon, the arrow’s height decreases by $1$.

The sharpshooter can shoot an arrow at any height.

Find the minimum number of arrows the sharpshooter needs to shoot.

Input Format

The first line contains one integer $n$.

The next line contains $n$ integers $h_i$.

Output Format

Only one line with one integer, representing the minimum number of arrows the sharpshooter needs to shoot.

5
2 1 5 4 3

2

5
1 2 3 4 5

5

5
4 5 2 1 4

3

Hint

Sample 1 Explanation

First shoot the balloon at height $5$, then shoot the balloon at height $2$.

Constraints and Limits

• For $40\%$ of the testdata, $n \le 5\times 10^3$ is guaranteed.
• For $100\%$ of the testdata, $1 \le n, h_i \le 10^6$ is guaranteed.

Notes

This problem is worth $100$ points.

This problem is translated from Croatian Open Competition in Informatics 2015/2016 Contest #1 T3 BALONI。

Translated by ChatGPT 5