Chain Spell Scoring

Little Dou loves playing games. In one game he faces the following scenario: There are n monsters with distinct health values \(a_i\) (i.e. each monster has a unique positive integer health). He has an infinite number of cards called "Profanation". When one card is used, its effect is to deal \(1\) point of damage to every monster. If at least one monster dies as a result of a cast (i.e. its health becomes 0), the spell is cast again automatically. We say that a monster dies when its health becomes 0.

Moreover, when Little Dou uses one Profanation card (which may trigger several casts), he scores points as follows. Let \(K\) be the total number of casts required to kill all monsters if one were to continue casting manually until every monster is dead. (Note that since every cast reduces each alive monster's health by 1, we have \(K = \max(a_i)\).)

Now, during the chain of casts initiated by one card, in every cast the damage is dealt to all monsters that are still alive. For each cast, if a monster is hit while its current health is \(x\) (i.e. right before taking the 1 point of damage), then that hit produces a contribution of \(x^K\) to the score. The total score is the sum of the contributions from all casts that actually occur.

The spell casting chain is triggered as follows:

• The first cast always occurs.
• For each subsequent cast (i.e. the \(t\text{-th}\) cast for \(t \ge 2\)), the cast is performed if and only if at least one monster was killed in the previous cast. A monster dies in the \(t-1\text{-th}\) cast if its health right before that cast was exactly \(1\); note that a monster’s current health at cast \(t\) is \(a_i - (t-1)\) if it has not been killed yet.
• The process stops when a cast does not kill any monster or when all monsters are dead.

Input and scoring example explanation:

Let \(K = \max(a_i)\) and let the chain length \(L\) be determined by the following: if \(1\) is not among the \(a_i\) then no monster dies in the first cast and \(L = 1\); otherwise, if the monsters contain a consecutive block of integers starting from 1 up to \(m\) (with \(m \le K\)), then the chain will continue for \(m+1\) casts, except that if \(m = K\) then the process stops when all monsters are dead (so \(L = K\)).

The total score is computed as follows:

[ \text{score} = \sum_{t=1}^{L} ; \sum_{{i: a_i \ge t}} (a_i - t + 1)^K. ]

For example:

• Case 1: Input: n = 1, a = [1]. Here \(K = 1\) and the first cast kills the monster. Score = \(1^1 = 1\).
• Case 2: Input: n = 2, a = [1, 2]. Here \(K = 2\).
  Cast 1: Monster healths: 1 and 2, contributions: \(1^2 + 2^2 = 1 + 4 = 5\); the monster with health 1 dies so a second cast occurs.
  Cast 2: Only the monster with initial health 2 is alive (its health becomes \(2-1=1\)); contribution: \(1^2 = 1\); total score = 5 + 1 = 6.
• Case 3: Input: n = 3, a = [1, 3, 4]. Here \(K = 4\).
  Cast 1: Healths: 1, 3, 4; contribution: \(1^4 + 3^4 + 4^4 = 1 + 81 + 256 = 338\); monster with health 1 dies so cast 2 occurs.
  Cast 2: Alive monsters: with initial 3 and 4 become \(3-1=2\) and \(4-1=3\); contribution: \(2^4 + 3^4 = 16 + 81 = 97\); total score = 338 + 97 = 435.

inputFormat

The first line contains an integer n representing the number of monsters. The second line contains n space‐separated positive integers \(a_1, a_2, \dots, a_n\) (each \(a_i\) is distinct) representing the health of each monster.

outputFormat

Output a single integer which is the total score accumulated according to the rules described.

sample

1
1

1