Uolevi has lost three months worth of his salary on bad NFT trades. Now he is coping with his poor life decisions by calculating how ridiculously rich he could be if he had just timed his trades right. He would buy a Lamborghini if he had all that money. Or maybe even a Bugatti. He looks at the price history of a particular monkey PNG. The price was p_i Eekoins at moment i. Find out how unbelievably much money he could have made just by trading this one NFT! Note that Uolevi can buy and sell the picture multiple times. He does not own it initially.

Input

The first line contains a single integer n. The second line contains n integers p_1,\,p_2,\dots,\,p_n.

Output

Print the maximum number of Eekoins Uolevi could have earned.

Constraints

• 1 \leq n \leq 10^5
• 0 \leq p_i \leq 10^9

Example 1

Input:

5
10 4 7 10 0

Output:

6

Example 2

Input:

10
2 4 10 10 6 5 4 0 4 3

Output:

12

Example 3

Input:

8
0 1000000000 0 1000000000 0 1000000000 0 1000000000

Output:

4000000000