Amplifiers

You have a sequence of ~N~ natural numbers ~(1 \le N \le 200.000)~, ~A_i\;(1 \le i \le N, \; 1 \le A_i \le 10^9)~.

In a continuous subrange of the numbers, let's say from ~L~ to ~R~ (where ~1 \le L \le R \le N~), you can apply an amplifier. The amplifier increases all the numbers ~A_i~ within the range ~(L \le i \le R)~ by one, but it can ONLY be used if all these numbers are equal.

Problem

Write a program to calculate the minimum number of amplifiers needed (applied one after the other) to make all numbers in the sequence equal.

Be careful because the number of amplifiers can be very large...

Input File

The first line of the input contains the integer ~N~. The second line contains ~N~ integers ~A_i~, separated by spaces.

Output File

The single line of output should contain only one integer: the minimum number of amplifiers needed to make all numbers in the sequence equal.

Examples of Input - Output Files:

1st

STDIN (amplifiers.in)

3
1 3 2

STDOUT (amplifiers.out)

3

2nd

STDIN (amplifiers.in)

4
1 2 4 2

STDOUT (amplifiers.out)

5

3d

STDIN (amplifiers.in)

5
3 1 4 1 1

STDOUT (amplifiers.out)

6

Constraints

• ~1 \le N \le 200.000~.
• ~1 \le A_i \le 10^9~.