Tom rất yêu thích việc liệt kê các dãy con (đặc biệt là các dãy con tăng) của một dãy số nguyên. Ta gọi ~A'~ là một dãy con tăng của dãy ~A~ nếu ~A'~ thu được bằng cách bỏ đi một số phần tử của ~A~, giữ nguyên thứ tự các phần tử còn lại và các phần tử trong ~A'~ được sắp xếp theo thứ tự tăng nghiêm ngặt.

Ví dụ: Cho dãy ~A = [6, 1, 9, 5, 8, 5]~. Các dãy ~[1, 5, 8]~ và ~[1, 8]~ là dãy con tăng của ~A~ nhưng ~[1, 5, 5]~ và ~[6, 1, 5]~ thì không phải là dãy con tăng của ~A~.

Với niềm đam mê tìm hiểu các con số, Tom định nghĩa độ khó của một số nguyên là tích các chữ số của nó.

Ví dụ: Hai số ~1234~ và ~813~ đều có độ khó bằng ~24~, còn số ~8~ có độ khó bằng chính nó.

Tom viết ra một dãy số ~A~ nguyên ngẫu nhiên, không có phần tử âm và đố Been tìm ra độ khó lớn nhất của dãy con tăng nghiêm ngặt trong dãy ~A~. Biết rằng độ khó của một dãy số được quy ước là tổng độ khó của tất cả các phần tử trong dãy đó. Các bạn hãy lập trình giúp Been nhé!

Yêu cầu: Cho dãy ~A~ gồm ~N~ số nguyên không âm ~A_1, A_2, \ldots, A_N~. Tìm độ khó lớn nhất của dãy con tăng trong dãy ~A~.

Input

Đọc từ tệp văn bản DAYCON.INP gồm hai dòng:

• Dòng 1: Ghi số nguyên dương ~N~ (~1 \le N \le 2 \times 10^5~);
• Dòng 2: Ghi ~N~ số nguyên không âm ~A_1, A_2, \ldots, A_N~ (~0 \le A_i \le 10^9~; ~i = 1, 2, \ldots, N~).

Output

Ghi ra tệp văn bản DAYCON.OUT một số nguyên là kết quả cần tìm.

Sample Input 1

5
5 101 54 123 56

Sample Output 1

55

Giải thích: Dãy ~[5, 54, 56]~ có độ khó lớn nhất trong số các dãy con tăng. Độ khó của nó là ~5 + 20 + 30 = 55~.

Giới hạn

• ~1 \le N \le 2 \times 10^5~;
• ~0 \le A_i \le 10^9~.

Subtask:

• Subtask 1: Có 20% số test ứng với 20% số điểm có ~N \le 20~;
• Subtask 2: Có 20% số test ứng với 20% số điểm có ~N \le 2000~;
• Subtask 3: Có 60% số test ứng với 60% số điểm có ~N \le 2 \times 10^5~.