ML

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 256 мегабайтів

Дано масив $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$ , а мінімальне значення функції.

Вхідні дані

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

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

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

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Вхідні дані #3

Відповідь #3

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

Відправки 1

Коефіцієнт прийняття 100%