채소 기르기는 즐거워
시간 제한2초메모리 제한512 MB
한 줄로 심긴 N개의 식물을 인접한 두 개씩 교환해, 모든 식물이 왼쪽 구간의 최댓값이거나 오른쪽 구간의 최댓값이 되도록 만드는 최소 교환 횟수를 구한다.
문제
가정 채소 재배가 취미인 JOI는 매년 자신의 밭에서 IOI풀이라는 식물을 기른다. JOI의 밭은 동서 방향으로 늘어선 N개의 구획으로 나뉘어 있고, 서쪽부터 1번부터 N번까지 번호가 붙어 있다. IOI풀은 모두 N그루 있으며, 각 구획에 한 그루씩 심어져 있다. 구획 i에 심어진 IOI풀은 봄이 되면 키 hi까지 자라고, 그 뒤로는 자라지 않는다.
봄이 되어 상태를 보러 간 JOI는 IOI풀의 배치가 예정과 다른 배치가 되어 있는 것을 알아챘다. IOI풀은 햇빛을 많이 필요로 하는 식물이라, 어떤 구획에 심어진 IOI풀에 대해 그 구획보다 번호가 작은 구획과 번호가 큰 구획 양쪽 모두에 그 IOI풀보다 키가 큰 IOI풀이 있으면, 그 IOI풀은 여름이 되기 전에 시들어 버린다. 즉, 어떤 IOI풀도 시들지 않게 하려면 다음 조건이 만족되어야 한다.
-
2 ≤ i ≤ N − 1을 만족하는 어떤 정수 i에 대해서도, 다음 두 조건 중 적어도 하나가 성립한다.
- 1 ≤ j ≤ i − 1을 만족하는 모든 정수 j에 대해, hj ≤ hi를 만족한다.
- i + 1 ≤ k ≤ N을 만족하는 모든 정수 k에 대해, hk ≤ hi를 만족한다.
IOI풀은 매우 비싸기 때문에, 어떤 IOI풀도 시들지 않게 JOI는 IOI풀의 순서를 바꾸기로 했다. IOI풀은 매우 크고 섬세한 식물이라, JOI는 인접한 두 IOI풀의 순서를 바꾸는 것밖에 할 수 없다. 즉, 1번의 조작으로 JOI는 구획 i (1 ≤ i ≤ N − 1)를 임의로 하나 골라, 구획 i의 IOI풀과 구획 i + 1의 IOI풀을 바꿀 수 있다. 여름이 다가올수록 시들 가능성이 높아지므로, 모든 IOI풀이 시들지 않게 하는 데 필요한 조작 횟수의 최솟값을 알고 싶다.
JOI의 밭의 구획 수와 각 IOI풀의 키 정보가 주어졌을 때, 모든 IOI풀이 시들지 않게 순서를 바꾸는 데 필요한 조작 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
표준 입력에서 다음 입력을 읽는다.
- 1번째 줄에는 정수 N이 쓰여 있다. N은 JOI의 밭의 구획 수를 나타낸다.
- 이어지는 N개의 줄에는 IOI풀의 키에 관한 정보가 쓰여 있다. 이 줄들 중 i번째 줄 (1 ≤ i ≤ N)에는 정수 Di가 쓰여 있다. Di는 구획 i에 심어진 IOI풀이 봄이 된 시점의 키를 나타낸다.
출력
표준 출력에, 필요한 조작 횟수의 최솟값을 나타내는 정수를 1줄로 출력하시오.
제한
- 3 ≤ N ≤ 300 000.
- 1 ≤ Di ≤ 1 000 000 000.