Unique stock counts: hints, no solution

A shop tracks how many units of each product are on the shelf. The manager wants every product to show a different count. The only allowed change is to remove one unit from a product at a time, and a count can go down to 0 but not below. Given the current counts, return the fewest single-unit removals needed so that no two products have the same count. If it is impossible, return -1. A shelf whose counts are already all different needs no removals.

Examples

Input

stock = [5, 5, 3, 3, 3]

Output

4

Note

The counts can become 5, 4, 3, 2 and 1, which takes 0 + 1 + 0 + 1 + 2 removals.

Input

stock = [0, 0]

Output

-1

Note

Two products cannot both hold 0 and cannot go lower.

Input

stock = [4, 1, 9]

Output

0

Constraints

• 0 <= stock.length <= 30000
• 0 <= stock[i] <= 100000

Hint 1: a nudge

When two products hold the same count, one of them has to give up units. Which one should it be, and how far down does it need to go?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing