아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Перераспределение камней

면접 대비

시간 제한2초메모리 제한1024 MB

요약
서로 다른 정수 위치 n곳에 놓인 돌들을 연속한 n칸에 모으기 위한 최소 이동 횟수를 구한다.
난이도

보통10점 중 6점

유형
정렬, 그리디, 수학
정답자
아직 제출이 없습니다

문제

Как известно, у красавицы и чудовища не все сразу было хорошо. Эта история как раз про это. Как только красавица стала пленницей в замке чудовища, он дал ей первое, но сразу же очень ответственное задание.

Перед красавицей стояло бесконечное количество сундуков, выставленных в линию и пронумерованных целыми числами от −∞-\infty до ∞\infty. В nn сундуках лежали волшебные камни, способные как убивать, так и воскрешать кого угодно, остальные же сундуки были пустые. Задание красавицы состояло в перекладывании камней из сундуков так, чтобы они все в конце концов лежали в nn различных сундуках с последовательными номерами. За одно перекладывание красавица могла взять камень из любого сундука и переложить его в любой другой не занятый камнем сундук.

Конечно, красавице захотелось как можно быстрее выполнить ее задание, поэтому она решила минимизировать количество перекладываний. С просьбой найти число этих перекладываний она обратилась к великому волшебнику Мерлину, воззвав к нему о помощи. Однако, даже Мерлин не смог справиться с этой задачей, и ему пришлось проделать долгое путешествие сквозь пространство и время, чтобы попросить помощи у вас. Помогите волшебнику решить задачу красавицы!

입력

В первой строке содержится число nn --- количество сундуков с волшебными камнями (1≤n≤1051 \le n \le 10^5).

Во второй строке содержатся nn чисел a_ia\_i --- номера сундуков с камнями (−109≤a_i≤109-10^9 \le a\_i \le 10^9). Гарантируется, что в каждом сундуке лежит не более одного камня.

출력

В единственной строке выведите минимальное количество перекладываний, которое требуется, чтобы разместить все nn камней в nn различных сундуках с последовательными номерами.

힌트

В первом тестовом примере подходит например такой алгоритм действий:

  • Переложить камень из сундука -2 в сундук 2
  • Переложить камень из сундука 7 в сундук 5

Также можно вторым действием переложить камень из сундука 7 в сундук 0.

예제1

  1. 예제 1

    입력
    5
    3 1 -2 4 7
    
    예상 출력
    2