E. Evil Capitalist
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today, Colin and Eva learned about exploitation in their "Basic Principles of Marxism" course. That night, Colin dreamed that he was a poor worker being exploited by the capitalist Eva without even realizing it.

Suppose you are an evil capitalist who employs $$$n$$$ exploited workers, numbered from $$$1$$$ to $$$n$$$. Worker $$$i$$$ currently earns $$$a_i$$$ yuan. Under your strict supervision, the workers cannot tell one another their salaries. You thought this arrangement would last forever, but the workers have begun to feel exploited and are planning to strike!

Without their labor, you cannot maintain your luxurious lifestyle. You therefore decide to raise some salaries to stop the protest. Initially, every worker is unsatisfied. You must arrange two-person chats until either all workers are satisfied or exactly one worker remains unsatisfied. In the latter case, nobody else remains to join that worker in a protest.

To arrange a chat, choose two unsatisfied workers $$$x$$$ and $$$y$$$ and temporarily allow them to reveal their salaries to each other:

  • If $$$a_x=a_y$$$, both workers feel that they have been treated equally and become satisfied.
  • If $$$a_x \gt a_y$$$, worker $$$x$$$ becomes satisfied. Worker $$$y$$$, however, realizes that they have been treated differently. You must increase worker $$$y$$$'s salary to $$$a_x$$$, paying $$$a_x-a_y$$$ yuan and setting $$$a_y=a_x$$$. Worker $$$y$$$ remains unsatisfied.
  • Similarly, if $$$a_y \gt a_x$$$, worker $$$y$$$ becomes satisfied. You must pay worker $$$x$$$ an additional $$$a_y-a_x$$$ yuan and set $$$a_x=a_y$$$, while worker $$$x$$$ remains unsatisfied.

As an evil capitalist, you want to spend as little as possible. Find the minimum total amount of money required to achieve your goal.

Input

The first line contains one integer $$$n$$$ ($$$1\le n\le 2\times 10^5$$$), the number of workers.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le 10^9$$$), where $$$a_i$$$ is the current salary of worker $$$i$$$.

Output

Output a single integer: the minimum amount of money you need to spend.

Example
Input
4
100 101 1 101
Output
1
Note

First, let workers $$$1$$$ and $$$2$$$ talk. Worker $$$2$$$ becomes satisfied, and you pay worker $$$1$$$ one yuan, making $$$a_1=101$$$.

Then let workers $$$1$$$ and $$$4$$$ talk. Because their salaries are equal, they both become satisfied.

Only worker $$$3$$$ remains unsatisfied, so the goal has been achieved.