Trong một đợt đi du lịch ở VT, sáng sớm ~n0th1gn~ thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của ~n0th1gn~ như sau: Ban đầu từ chuỗi rỗng, không có vỏ ốc; khi gặp một vỏ ốc mới, có thể lấy để xâu vào một trong hai đầu của chuỗi hoặc bỏ đi không lấy; cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu chuỗi đến cuối chuỗi, các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt.

Yêu cầu

Cho trước dãy ~a_1, a_2, … , a_n~ là kích thước của các vỏ ốc mà ~n0th1gn~ lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được chuỗi gồm nhiều vỏ ốc nhất.

Dữ liệu

Dòng 1: Chứa số nguyên dương ~n~.
Dòng 2: Chứa số nguyên cách nhau bởi dấu cách lần lượt là thời điểm học sinh tới trường, các thời điểm này là số nguyên không âm và không quá ~10^9~.

Kết quả

Một số nguyên duy nhất là tổng thời gian chờ đợi (tính bằng giây) của n học sinh.

Giới hạn

\(n \leq ~10^5~, ∀i: |a_i| \leq ~10^9~\).

Input

5
4 4 5 3 1

Output

4

-40% số điểm ứng với các test có \(n \leq 20\).
-30% số điểm ứng với các test có thỏa mãn \(20 \leq n \leq 1000\).
-30% số điểm ứng với các test có thỏa mãn \(1000 \leq n \leq ~10^5~\).