과제 마감
시간 제한1초메모리 제한512 MB
단위 시간이 걸리는 N개의 과제에 각각 마감 시각이 주어질 때, 모든 과제를 제때 끝내도록 순서를 바꾸는 데 필요한 인접 교환의 최소 횟수를 구하고 불가능하면 -1을 출력한다.
문제
Bob에게는 마감 기한 안에 끝내야 하는 프로그래밍 과제가 N개 있다. 과제 i는 한 시간 단위만 쓰면 끝낼 수 있지만, 지금부터 di (1 ≤ di ≤ N) 시간 단위 안에 끝내야 한다.
Bob은 수열 a1, a2, ..., aN으로 표현되는 순서로 과제를 푼다. a1은 처음 푸는 과제, a2는 두 번째로 푸는 과제이고, 이런 식으로 이어진다. Bob의 원래 계획은 수열 1, 2, ..., N이다. 한 번의 교환 연산으로 Bob은 이 수열에서 인접한 두 수를 맞바꿀 수 있다. 이 수열을 모든 과제를 제때 끝내는 수열로 바꾸는 데 필요한 최소 교환 횟수는 얼마인가?
입력
첫째 줄에 정수 N (1 ≤ N ≤ 200 000)이 주어진다. 다음 줄에 N개의 정수 d1, d2, ..., dN (1 ≤ di ≤ N)이 공백으로 구분되어 주어진다.
출력
Bob이 모든 과제를 제때 풀기 위해 필요한 최소 교환 횟수를 한 정수로 출력한다. 불가능하면 -1을 출력한다.