Dãy con tăng

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

Dữ liệu vào 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, A_3, \ldots, A_N\) (\(0 \le A_i \le 10^9\); \(i = 1, 2, \ldots, N\)).

Ràng buộc:

• 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\).

Output

In ra một số nguyên là kết quả cần tìm.

Example

Input:

5
5 101 54 123 56

Output:

55

Note

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\).