단체 사진

연수 캠프가 끝날 때 N명의 참가자가 모여 단체 사진을 찍는다. 참가자는 키 순서대로 1번부터 N번까지 번호가 붙어 있다. 참가자 h의 키는 h이다 (1 ≤ h ≤ N).

참가자는 계단 위에 서서 사진을 찍는다. 계단에는 N개의 칸이 있다. 칸은 낮은 곳에서 높은 곳으로 1번부터 N번까지 번호가 붙어 있다.

칸 i + 1은 칸 i보다 2만큼 높다 (1 ≤ i ≤ N − 1). 계단의 칸이 좁아서, 각 칸에는 참가자 한 명만 선다. 참가자들이 일렬로 늘어서면 단체 사진을 찍는다.

곧 단체 사진을 찍는다. 지금은 각 칸에 참가자 한 명이 서 있다. 참가자 H_i가 칸 i에 서 있다 (1 ≤ i ≤ N). 그런데 참가자들의 키 차이가 너무 커서, 지금 순서대로 사진을 찍으면 다른 참가자에 가려 보이지 않는 참가자가 생길 수 있다. 그래서 모든 참가자의 머리가 최소한 사진에 나오도록 참가자의 순서를 바꾸려고 한다. 다시 말해, 다음 조건을 만족해야 한다.

칸 i에 있는 참가자의 키를 a_i라고 하자 (1 ≤ i ≤ N). 그러면 모든 i (1 ≤ i ≤ N − 1)에 대해 부등식 a_i < a_{i+1} + 2가 성립해야 한다.

이웃한 두 참가자만 교환할 수 있다. 즉, 한 번의 연산으로 칸 i (1 ≤ i ≤ N − 1)를 임의로 골라 칸 i의 참가자와 칸 i + 1의 참가자를 교환한다.

위 조건을 만족하도록 만들 때 연산 횟수를 최소화하려고 한다.

참가자의 순서가 주어졌을 때, 필요한 최소 연산 횟수를 계산하는 프로그램을 작성하시오.

표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.

N
H1 · · · HN

표준 출력에 한 줄을 쓴다. 출력에는 최소 연산 횟수가 들어가야 한다.

• 3 ≤ N ≤ 5 000.
• 1 ≤ Hi ≤ N (1 ≤ i ≤ N).
• Hi ≠ Hj (1 ≤ i < j ≤ N).