Cho một dãy ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \leq a_i \leq 10^5, 1 \leq i \leq n \leq 10^5)~.

Yêu cầu: Tìm số ~a_i~ có số ước nguyên dương nhiều nhất, nếu có nhiều số như vậy thì in ra số xuất hiện đầu tiên trong các số đó.

INPUT

• Dòng đầu tiên là số nguyên dương ~n~
• Dòng tiếp theo là ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Mỗi số cách nhau một khoảng trắng.

OUTPUT

• Ghi ra một số nguyên dương duy nhất là kết quả tìm được.

SAMPLE INPUT 1

5
10 6 8 7 2 

SAMPLE OUTPUT 1

10

SAMPLE INPUT 2

4
10 6 8 7

SAMPLE OUTPUT 2

10

SUBTASKS

• Có ~80\%~ số điểm ứng với ~(1 \leq n \leq 10^3; 1 \leq a_i \leq 10^3)~
• ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Cho một xâu ký tự ~S~ có độ dài ~N~ gồm các ký tự chữ cái: a...z và chữ số: 0...9. Khi loại bỏ các ký tự chữ cái, ta sẽ nhận được các xâu con chỉ bao gồm các ký tự chữ số, từ đó ta nhận được một dãy các số nguyên. Ví dụ xâu ~S =~ 35a500b0786c, khi loại các ký tự chữ cái ta nhận được các số 35; 500; 786 (số 0786 có 0 ở đầu nên số ta nhận được là số 786).

Yêu cầu: Tìm số lớn nhất trong dãy các số nguyên nêu trên.

INPUT

• Dòng duy nhất chỉ có 1 dòng ghi xâu ký tự ~S~ (~3 \leq N \leq 10^5~).

OUTPUT

• Ghi ra số lớn nhất tìm được.

SAMPLE INPUT

35a500b0786c

SAMPLE OUTPUT

786

SUBTASKS

• Có ~20\%~ số điểm ứng với: các số xuất hiện trong ~S~ có giá trị không vượt quá ~9~;
• Có ~40\%~ số điểm ứng với: các số xuất hiện trong ~S~ có giá trị không vượt quá ~10^2~;
• ~40\%~ số điểm còn lại không có giới hạn gì thêm.

Một số nguyên dương được gọi là số đặc biệt nếu nó có đúng ~3~ ước nguyên dương đôi một khác nhau.

Yêu cầu: Cho ~M~ cặp số nguyên dương ~(a; b)~, hãy đếm số lượng số đặc biệt ~x~ thoả mãn ~a \leq x \leq b~.

INPUT

• Dòng đầu là số nguyên dương ~M~ ~(1 \leq M \leq 10^5)~;
• ~M~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~a, b~ cách nhau bởi một khoảng trắng ~(1 \leq a \leq b \leq 10^6)~.

OUTPUT

• Ghi ra kết quả gồm ~M~ dòng, mỗi dòng là kết quả tương ứng tìm được.

SAMPLE INPUT

2
1 10
1 100

SAMPLE OUTPUT 1

2
4

SUBTASKS

• Có ~20\%~ số điểm ứng với ~(1 \leq M \leq 10^2; 1 \leq b \leq 10^3)~;
• Có ~30\%~ số điểm ứng với ~(1 \leq M \leq 10^3; 1 \leq b \leq 10^5)~;
• ~50\%~ số điểm còn lại không có giới hạn gì thêm.

Cho một dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^6, 1 \leq i \leq n \leq 10^5~).

Xét các dãy con là dãy các phần tử liên tiếp nhau của dãy ban đầu, mà trong đó các phần tử không giảm (~a_i \leq a_{i+1} \leq \ldots \leq a_j; 1 \leq i \leq j \leq n~).

Yêu cầu: Tìm dãy con có tổng các phần tử là lớn nhất trong các dãy con trên, nếu có nhiều dãy con thỏa mãn thì in ra các dãy con lần lượt theo vị trí xuất hiện, mỗi dãy con in trên một dòng.

INPUT

• Dòng đầu tiên ghi số nguyên dương ~n~;
• Dòng tiếp theo ghi ~n~ số nguyên dương, mỗi số cách nhau một khoảng trắng.

OUTPUT

• Dòng đầu tiên ghi tổng các phần tử của một dãy con tìm được theo yêu cầu;
• Các dòng tiếp theo, mỗi dòng ghi ra các phần tử của một dãy con tìm được.

SAMPLE INPUT 1

10
2 2 3 4 6 6 7 7 8 8 

SAMPLE OUTPUT 1

53
2 2 3 4 6 6 7 7 8 8

SAMPLE INPUT 2

11
4 7 4 5 7 4 9 3 3 4 6

SAMPLE OUTPUT 2

16
4 5 7
3 3 4 6

SUBTASKS

• Có ~20\%~ số điểm ứng với ~n = 10~ và dãy ban đầu là một dãy không giảm;
• Có ~20\%~ số điểm ứng với ~(11 \leq n \leq 200)~;
• Có ~20\%~ số điểm ứng với ~(201 \leq n \leq 10^3)~;
• Có ~40\%~ số điểm còn lại ứng với ~(10^3 < n \leq 10^5)~.