Có \(N\) học sinh đứng thành một hàng dọc. Mỗi học sinh i có điểm số \(r_i\). Giáo viên muốn phát kẹo cho các em theo quy tắc:

• Mỗi học sinh nhận ít nhất 1 cái kẹo.
• Học sinh có điểm số cao hơn học sinh bên cạnh phải nhận nhiều kẹo hơn.

Hãy tìm tổng số kẹo ít nhất cần phát.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(r_1, r_2, \dots, r_N\) (\(1 \le r_i \le 10^5\)).

Kết quả ra

• In ra tổng số kẹo ít nhất.

Ví dụ

Input

5
1 2 3 2 1

Output

9

Ràng buộc & Subtasks