Trong những ngày cách li xã hội do bệnh dịch Cô-rô-na, "Hải" phải tuân thủ cách li trong nhà, do quá buồn chán không được đi chơi nên "Hải" nghĩ ra một trò chơi thú vị trên dãy số và đố "Hiếu" là :

Cho một dãy các phần tử nguyên đôi một khác nhau.

Nhiệm vụ của "Hiếu" là hoán đổi vị trí 2 phần tử bất kì cho đến khi dãy số tăng dần hoặc giảm dần.

Nghe thì có vẻ dễ dàng nhưng sau một hồi giải đố thì "Hiếu" kiệt sức vì số lần hoán đổi rất nhiều.

Do quá bí và mỗi người đều cách li tại nhà nên "Hiếu" chơi ăn gian lên mạng hỏi các bạn cách giải đố là các bạn hãy tìm hộ "Hiếu" số lần hoán đổi ít nhất để được một dãy tăng dần hoặc giảm dần.

Các bạn hãy giúp "Hiếu" nhé !

Input

• Dòng đầu chứa số lượng phần tử dãy n (1<=n<=10^5)
• Dòng thứ 2 chứa n số nguyên a[i] (1<=a[i]<=2 * 10 ^ 9)

Ouput

• Một số nguyên thỏa mãn yêu cầu bài trên.

Example1

Input

4
2 5 3 1

Output

2

Example2

Input

5
3 4 2 5 1

Output

2

Giải thích :
Ex1 . Hoán đổi 2 và 1 được: 1 5 3 2
Hoán đổi 5 và 2 được: 1 2 3 5
--> Số lần hoán đổi ít nhất 2

Ex2. Hoán đổi 5 và 3 được: 5 4 2 3 1
Hoán đổi 2 và 3 được: 5 4 3 2 1
--> Số lần hoán đổi ít nhất 2