Background

Thanks to whk, a top-tier expert, and Fan Ju (bx).

Although Fanfan is very strong in academic subjects, during the New Year he does not want to put too much pressure on other students of the same age, so he plans to tamper with his exam results over the year.

Problem Description

Looking at his grades soaring like a giant dragon, when the New Year arrives, Fanfan cannot help but sing Love You.

This year he has a total of $n$ exams, and in the $i$-th exam his rank is $a_i$.

This creates pressure for other classmates, so he wants to reorder his $n$ ranks so that the exam with the largest improvement has the smallest possible improvement in rank, so that he can hide his true strength.

For the $i$-th and the $(i+1)$-th exams ($1\le i < n$), his improvement in rank is $a_i-a_{i+1}$. If this value is negative, it means he got worse.

Please help him.

Input Format

There are two lines of input.

The first line contains an integer $n$.

The second line contains $n$ integers, separated by spaces. The $i$-th integer is $a_i$.

Output Format

Output one line containing one integer, which is the answer.

2
1 1

0

4
2 4 1 3

-1

Hint

Sample 1 Explanation

If Fanfan does not change the original exam sequence, then from the first to the second exam he improves by $0$ places (the rank does not change).

Sample 2 Explanation

Fanfan can reorder his exam ranks as $1,2,3,4$. Then for every exam he improves by $-1$, so the answer is $-1$.

This problem uses bundled testdata.

Constraints

• For $30\%$ of the testdata, $n\le 10$ is guaranteed.

• For $50\%$ of the testdata, $n\le 5000$ is guaranteed.

• For the remaining $20\%$ of the testdata, $a_i\le 2$ is guaranteed.

• For $100\%$ of the testdata, $2\le n\le 10^6$ and $1\le a_i\le 10^9$ are guaranteed.

Translated by ChatGPT 5