Cho một dãy số nguyên gồm ~N~ phần tử: ~a_1, a_2, ..., a_N~. Một đoạn con ~[L, R]~ là dãy gồm các phần tử liên tiếp ~a_L, a_{L+1}, ..., a_R~ với ~(1 \leq L < R \leq N)~, đoạn con ~[L, R]~ được gọi là quan trọng nhất nếu:

• Phần tử đầu bằng phần tử cuối ~A_L = A_R~
• Tổng các phần tử của đoạn con là lớn nhất có thể.

Input

• Dòng 1: Gồm số nguyên dương ~N~.
• Dòng 2: Gồm dãy ~A_1, A_2, ..., A_N~ (~0 < A_i \leq 10^3, 1 \leq i \leq N)~, mỗi số cách nhau một khoảng trắng.

Output

Tìm một đoạn con quan trọng nhất và tính tổng các phần tử trong đoạn con đó.

Sample Test

Input:

6
2 2 2 3 10 3

Output:

16

Đoạn con quan trọng nhất ~3, 10, 3~ có tổng các phần tử là ~16~

Note

• 40% số test tương ứng với 40% số điểm có ~2 \leq N \leq 10^2~
• 30% số test tương ứng với 30% số điểm có ~2 \leq N \leq 10^3~
• 30% số test tương ứng với 30% số điểm có ~2 \leq N \leq 10^6~

Cho số nguyên dương ~N~. Trong tất cả các cặp số nguyên dương ~(a, b)~ thoả mãn ~a + b = N~, hãy tìm cặp số có LCM nhỏ nhất và cặp số có LCM lớn nhất.

LCM của hai số nguyên dương ~a~ và ~b~ là bội chung nhỏ nhất của chúng, hay nói cách khác, là số nguyên dương nhỏ nhất chia hết cho cả ~a~ và ~b~.

Input

Gồm một dòng duy nhất chứa số nguyên ~N~ (~2 \le N \le 10^9~).

Output

In ra trên một dòng hai số nguyên là LCM nhỏ nhất và LCM lớn nhất tìm được.

Scoring

• Subtask 1 (~40\%~ số điểm): ~n \le 10^6~.
• Subtask 2 (~60\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input:

10

Output

5 21