Đức có \(N\) túi kẹo được xếp thành một đường thẳng \((1 \leq N \leq 5000)\), túi kẹo thứ \(i\) có \(A_i\) viên kẹo \((1 \leq A_i \leq 10^9;1 \leq i \leq N)\) anh ta muốn các túi kẹo phải được xếp thành một dãy sao cho túi kẹo bên phải có số kẹo lớn hơn hoặc bằng túi kẹo bên trái. Vì không muốn thay đổi thứ tự các gói kẹo nên Đức lấy ra hoặc thêm vào các túi kẹo một số kẹo nhất định. Vì cần có thời gian suy nghĩ nên mỗi lần Đức chỉ thực hiện một thao tác lấy ra khỏi túi 1 viên kẹo hoặc thêm 1 viên kẹo vào túi. Hỏi cần bao nhiêu ít nhất bao nhiêu thao tác để Đức có thể thu được kết quả như mong muốn.

Input

• Dòng 1: Chứa số nguyên \(N\) là số túi kẹo của Đức
• Dòng 2: Chứa \(N\) số nguyên mỗi số cách nhau 1 kí tự trống lần lượt là số kẹo \(A_i\) của túi kẹo thứ \(i\)

Output

• Chứa 1 số nguyên duy nhất là số lần thực hiện thao tác của Đức

Subtask

Dựa trên bộ test, trong đề thi gốc không có phần giới hạn này.

• Subtask \(1: n \le 20\)
• Subtask \(2: n \le 1000, a \le 10^5\)
• Subtask \(3:\) giới hạn gốc

Example

3
4 3 6 

1

5
2 3 1 5 4 

3