Trek 2

You are planning a trek in the Waitākere Ranges. The Waitākere Ranges can be thought of as a collection of $N$ mountains. Each mountain has an assigned height. Your trek will consist of a series of mountains, which you must pick. You will start at the first mountain you pick, then walk to the second one you pick, and so on. You want some variety in the mountains you visit, so the enjoyment score of your trek is given by the difference between the height of the tallest mountain you climb, and the height of the shortest mountain you climb.

Find the maximum possible enjoyment score you can achieve. There are few restrictions on how your trek must be structured, you can pick as many or as few stops as possible (as long as you summit at least one mountain!), you can visit mountains in any order, and you can even visit mountains multiple times.

Input

• The first line will contain a single integer $N$, the number of mountains.
• The next $N$ lines will contain one integer each, with the $i$th integer representing the height of the $i$th mountain ($h_i$)

Output

• Output a single integer, the maximum possible enjoyment score you can achieve

Constraints

• $1 \le N \le 100{,}000$ - There are between one and 100 thousand mountains
• $0 \le h_i \le 100{,}000{,}000$ for all $i$ - The height of each mountain is an integer between zero and one hundred million

Subtasks

• Subtask 1 (13%): $N=1$ - There is exactly one mountain
• Subtask 2 (20%): $N=2$ - There is exactly two mountains
• Subtask 3 (31%): $N \le 1{,}000$ - There are at most 1000 mountains
• Subtask 4 (36%): No further constraints

Sample Explanations

Sample One Explanation

In this sample there are six mountains, with heights 3, 5, 11, 2, 5, 11. If, on your trek you go over the third, second, fifth, and fourth mountains in that order, the highest point you reach has height 11 (the third mountain). The lowest point you reach has height 2 (the fourth mountain). The difference in their height is $11-2=9$. This is the maximum possible enjoyment score, so we output 9.