ML

Execution time limit is 1 second

Runtime memory usage limit is 256 megabytes

Дано масив $a$ з $n$ цілих чисел.

Вам потрібно знайти таке число $x$ , при якому наступна функція мінімальна:

i = 1 \sum n ∣ a_{i} - (x + i - 1) ∣

Цю ж саму функцію можна записати як

∣ a_{1} - x ∣ + ∣ a_{2} - (x + 1) ∣ + ∣ a_{3} - (x + 2) ∣ + \dots + ∣ a_{n} - (x + n - 1) ∣

Тут $∣ x ∣$ — абсолютне значення $x$ . Наприклад, $∣ - 4∣ = 4$ , $∣9∣ = 9$ .

Проте виведіть не $x$ , а мінімальне значення функції.

Input

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ ).

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 1 0^{9}$ ).

Виведіть одне ціле число — мінімальне значення функції.

Input #1

Answer #1

Input #2

Answer #2

Input #3

Answer #3

Рішення, які правильно працюють для $n, a_{i} \leq 100$ , отримають принаймні $40$ балів.

Submissions 1

Acceptance rate 100%