Дат је природан број N и низ целих бројева a₁, a₂, …, a_N. У једној операцији могуће је одабрати произвољан елемент и повећати његову вредност за 1. Колико је најмање операција потребно да низ садржи тачно две различите вредности? Временска сложеност треба бити O(nlog n).

Улаз

У првом реду стандардног улаза налази се цео број N који представља број елемената низа.

У наредном реду налази се N целих бројева одвојених размаком, a₁, a₂, …, a_N, који представљају елементе низа.

Излаз

Исписати један број - минималан број операција потребних да низ садржи тачно две различите вредности.

Ограничења

• 2 ≤ N ≤ 2 ⋅ 5000
• 1 ≤ a_i ≤ 10⁶

Пример 1

Улаз

4
6 20 15 12

Излаз

11

Објашњење примера

Ако над првим елементом извршимо 6 операција (увећамо број 6 за 6) и над трећим елементом извршимо 5 операција (увећамо број 15 за 5) добијамо низ [12, 20, 20, 12] који садржи тачно две различите вредности. Може се показати да је од датог низа немогуће направити низ који садржи тачно две различите вредности користећи мање од 11 операција.

Пример 2

Улаз

5
2 2 2 2 2

Излаз

1

Објашњење примера

Пошто су све вредности једнаке, можемо над било којим елементом да применимо једну операцију и имаћемо тачно две различите вредности у низу.