Nhân dịp quốc tế thiếu nhi ~1~/~6~, nhà trường tổ chức phát kẹo cho học sinh. Để màn phát kẹo thêm phần hấp dẫn, lớp của ~Egg~ có một trò chơi nho nhỏ:

Cho dãy gồm ~n~ số nguyên dương, ~Egg~ được phép sắp xếp thứ tự các số trong dãy tuỳ ý. Số kẹo nhận được sẽ bằng tổng độ dài của các dãy con tăng ngặt dài nhất (không cần liên tiếp) kết thúc tại ~i~ với mọi ~1 \le i \le n~.

~Egg~ muốn nhận được số kẹo lớn nhất. Hãy giúp ~Egg~ nhé!

Input

• Dòng thứ nhất chứa số nguyên ~n~ là số lượng số trong dãy. (~1 \le N \le 2 \times 10^5~)

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~, mỗi số được ngăn cách nhau bởi một dấu cách. (~a_i \le 10^9~)

Output

• Ghi ra số kẹo lớn nhất ~Egg~ có thể lấy được.

Sample Input

3
1 3 2

Sample Output

6

Note

Giải thích test mẫu:

~Egg~ sẽ sắp xếp dãy các gói kẹo thành dãy ~\{1, 2, 3\}~.

Gọi ~f_i~ là độ dài của dãy con tăng ngặt dài nhất kết thúc tại ~i~, ta có ~f = \{1, 2, 3\}~.

Tổng độ dài các dãy con tăng ngặt dài nhất kết thúc tại ~i~ với mọi ~1 \le i \le n~ là ~6~, đây cũng là giá trị lớn nhất có thể đạt được.