URI Online Judge | 3175

Santa's Gifts

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

Santa is asking you to help him distribute gifts in an optimal way.

He gave you a list containing a number N, followed by N numbers gi, and told you that these are his notes regarding N children that he has been watching this year. Each of these N numbers represents how many good deeds a specific child has made.

Now he wants to distribute gifts, but he has to be fair regarding how many good deeds a child has made and how many gifts they will receive. He gave you the following three restrictions:

  1. Every child should receive at least 1 gift.
  2. For every pair of children A and B, such that they have made the same amount of good deeds, they should receive the same amount of gifts.
  3. For every pair of children A and B, such that child A has done more good deeds than child B, child A should get more gifts than child B.

For example, let's suppose that there are 3 children, and that the first child has made 1 good deed this year, the second has made 3 good deeds, and that the third child has made 1 good deed. One valid way to distribute gifts would be to give the first and third children 3 gifts each (because they have done the same amount of good deeds), and 5 gifts to the second child (because he has done more good deeds than the others). Notice that this distribution follow all the restrictions, but it's not the only, nor the most economic way to distribute the gifts.

After reading his notes, you should help Santa figure out what is the minimum total number of gifts to be sent to the children. You must remember to respect the restrictions, and also try to minimize the amount of gifts sent in total.

Input

The first line of input contains an integer N (1 ≤ N ≤ 104), representing for how many children you should distribute gifts to.

The second line of input contains N integers gi (1 ≤ gi ≤ 104, for every 1 ≤ iN), representing that the i-th child has done gi good deeds this year.

Output

You should print one line, containing one integer, representing the minimum total number of gifts that should be sent to these children.

Input Samples Output Samples

3
1 3 1

4

3
1 3 2

6