수열 정렬하기 4

길이 $N$의 수열 $A$가 정렬되어 있다는 것은 모든 $1 \leq i < N$에 대해 $A_i \leq A_{i+1}$이 성립한다는 뜻이다.

다음 연산을 $0$번 이상 적용할 수 있다. $1 \leq k \leq N$인 정수 $k$를 골라 $A_k$에는 을 더하고, 나머지 모든 원소에서는 을 뺀다.

연산 도중이나 연산 후에 원소가 음수가 되어도 상관없다. 어떤 수열이 주어져도 이 연산만으로 정렬된 상태로 만들 수 있다. 정렬에 필요한 연산의 최소 횟수를 구하라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

최소 연산 횟수를 출력한다.

• $1 \leq N \leq 100\,000$.
• $0\leq A_i\leq10^9$ ().