Tuấn là một học sinh đam mê lập trình và yêu thích kiến trúc. Trên đường đi học, Tuấn thường ngắm nhìn những ngôi nhà cao tầng.
Một hôm, cậu nảy ra một câu hỏi thú vị: "Nếu chọn ra một số ngôi nhà trên đường có chiều cao tăng dần (theo đúng thứ tự ban đầu), thì tổng chiều cao lớn nhất có thể đạt được là bao nhiêu? Và có bao nhiêu cách chọn ra như vậy?"

Cho dãy chiều cao của N ngôi nhà nằm liên tiếp trên một con đường.
Hãy giúp Tuấn tìm:

1. Tổng chiều cao lớn nhất của một số ngôi nhà có chiều cao tăng dần.
   (Các ngôi nhà không cần liên tiếp, nhưng phải giữ nguyên thứ tự).
2. Số lượng dãy khác nhau đạt được tổng chiều cao lớn nhất đó.
   (Hai dãy con được xem là khác nhau nếu khác nhau về vị trí của ít nhất một phần tử).

Input (file PHODEP.INP)

• Dòng 1: Số nguyên dương N (1 ≤ N ≤ 10^6) – số lượng ngôi nhà.
• Dòng 2: N số nguyên dương a1, a2,…, aN (1 ≤ ai ≤ 10^6) – chiều cao của các ngôi nhà theo thứ tự từ đầu đường đến cuối đường.

Output (file PHODEP.OUT)

• Dòng 1: Tổng chiều cao lớn nhất tìm được.
• Dòng 2: Số lượng dãy con thỏa mãn tổng chiều cao lớn nhất.

Giới hạn

• Có 10% số test (ứng với 10% số điểm) có N ≤ 20.
• Có 50% số test (ứng với 50% số điểm) có N ≤ 10^4.
• Có 40% số test (ứng với 40% số điểm) có N ≤ 10^6.

Example

PHODEP.INP

5
9 13 14 14 15

PHODEP.OUT

42
2

Giải thích: Có 2 dãy con tăng dần cùng đạt tổng 42: [13, 14, 15].

• Dãy 1: Các ngôi nhà có vị trí 2, 3, 5.
• Dãy 2: Các ngôi nhà có vị trí 2, 4, 5.