Điểm phạt của một dãy \(b\) gồm \(m\) số nguyên là số lượng vị trí \(i\) sao cho \(1 \leq i < m\) và \(b_i < b_{i + 1}\).

Cho dãy \(a\) gồm \(n\) số nguyên. Hãy chia dãy \(a\) thành hai dãy con sao cho mỗi phần tử của \(a\) thuộc một trong hai dãy và tổng điểm phạt của hai dãy là nhỏ nhất.

Dãy con của một dãy có thể thu được bằng cách xoá đi một vài (có thể không hoặc tất cả) phần tử của dãy.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\).

Output

• Một số nguyên duy nhất là tổng điểm phạt nhỏ nhất.

Example

5
1 2 3 4 5

3

5
3 3 3 3 3

0