Một người bạn của Marton là Cero có một mảng gồm ~N~ số nguyên dương. Đầu tiên, Cero viết số đầu tiên lên trên bảng. Sau đó, anh ấy viết số thứ hai sang bên trái hoặc bên phải của số đầu tiên. Tiếp theo, anh ấy viết số thứ ba sang bên trái hoặc bên phải của tất cả những số đã viết, và cứ như vậy cho tới hết dãy.

Marton hỏi Cero độ dài lớn nhất của dãy con tăng có thể tạo được là bao nhiêu (dãy con tăng không bắt buộc phải bao gồm các phần tử liên tiếp).

Anh ấy cũng muốn biết là có tổng cộng bao nhiêu dãy như vậy. Nói đúng hơn, nếu độ dài của dãy con tăng dài nhất có thể tạo thành là ~M~, thì anh ấy muốn biết tổng số lượng dãy con tăng với độ dài ~M~ của tất cả các dãy mà Cero có thể tạo ra.

Hai dãy Cero tạo ra được coi là khác nhau nếu chúng được tạo nên với ít nhất một bước khác với dãy còn lại.

Hai dãy con trong cùng một dãy tạo ra bởi Cero được coi là khác nhau khi có ít nhất một vị trí khác so với dãy con còn lại.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \leq N \leq 2 \times 10^5)~.
• Dòng tiếp theo gồm ~N~ số nguyên biểu diễn mảng số của Cera. Đảm bảo các số nhỏ hơn hoặc bằng ~10^9~.

Output

In ra một dòng duy nhất gồm hai số: độ dài của dãy con tăng dài nhất có thể tạo được và số lượng dãy con tăng có độ dài như vậy, lấy phần dư cho ~10^9+7~

Sample 1

Input

2 
1 1

Output

1 4

Giải thích

Dãy con tăng dài nhất có thể tạo được có độ dài ~1~ và có ~4~ dãy như vậy.

Cách tạo dãy thứ nhất: Viết số 1 đầu tiên, sau đó viết số 1 thứ hai sang bên phải. Dãy được tạo ra là 1 1; và có ~2~ dãy con tăng với độ dài ~1~ ở dãy đó là: 1 1 và 1 1.

Cách tạo dãy thứ hai: Viết số 1 đầu tiên, sau đó viết số 1 thứ hai sang bên trái. Dãy được tạo ra là 1 1; và có ~2~ dãy con tăng với độ dài ~1~ ở dãy đó là: 1 1 và 1 1.

Sample 2

Input

4 
2 1 3 4 

Output

4 1

Giải thích

Dãy con tăng dài nhất có thể tạo được có độ dài ~4~. Nó chỉ có thể tạo được khi dãy ban đầu được tạo ra là 1 2 3 4. Đối với dãy này, chỉ có duy nhất một dãy con tăng có độ dài ~4~ nên tổng số dãy con tăng dài nhất là ~1~.

Subtask

• ~6~ test có ~N \leq 20~
• ~4~ test tiếp theo có ~N \leq 1000~
• ~10~ test còn lại không có điều kiện gì thêm