단체사진 timer 2초 memory 1024MB

어느 합숙의 마지막 날, 합숙의 참가자 N명으로 집합 사진을 찍게 되었다. 참가자는 키가 낮은 순서로 1에서 N까지 번호가 매겨집니다. 참가자 h의 신장은 h이다 (1 ≤ h ≤ N).

집합 사진은 계단 위에 나란히 촬영한다. 이 계단은 단지 N 스테이지로 구성되며, 낮은 쪽부터 순서대로 1에서 N까지 번호가 매겨져 있다. 스테이지 i + 1은 스테이지 i보다 2만큼 높다 (1 ≤ i ≤ N - 1). 계단의 폭은 매우 좁기 때문에 각 단에 참가자가 한 명씩 서서 세로 일렬로 나란히 촬영한다.

얼마 지나지 않아 촬영이 진행되고 있으며 각 단계에 참가자가 서 있습니다. 현재 단계 i (1≤i≤N)에 서있는 참가자는 참가자 H_i다.

그러나 너무 많은 참가자의 키가 너무 다르기 때문에 이 순서로 사진에 나타나지 않는 참가자가 있을 수 있다. 그래서 당신은 참가자의 위치를 정렬하고 적어도 모든 사람의 머리의 상단이 찍히기를 원한다.

즉, 다음 조건이 충족되도록 하고 싶다.

• 스테이지 i (1≤i≤N)에 서있는 참가자의 신장을 a_i라고 한다면 이 때 모든 i (1≤i≤N-1)에 대해 a_i <a_{i + 1} + 2가 성립한다.

다만, 당신은 이웃하는 참가자의 위치를 바꿀 수밖에 없다. 즉, 1회의 조작에 있어서, 단계 i (1≤i≤N-1)를 임의로 하나 선택해, 단계 i의 참가자와 단계 i+1의 참가자를 교환할 수 있다.

가능한 한 적은 횟수로 이 작업을 수행하여 조건이 충족되도록 하십시오.

현재 참가자의 정렬 순서가 주어지면 필요한 조작 횟수의 최솟값을 찾는 프로그램을 작성하시오.