Nguồn: Học sinh Giỏi THPT Hà Nội năm 2013 - 2014

Cho số nguyên dương \(n\) và dãy số nguyên \(A\) gồm \(n\) phần tử \(a_1, a_2, ..., a_n\). Một cách chọn bộ \(2\) chỉ số \(i, j\) (\(1 \le i < j \le n\)) được gọi là tối ưu nếu \(D = a_j - a_i\) đạt giá trị lớn nhất.

Ví dụ: Dãy số nguyên gồm \(6\) số \(4, 2, 5, 8, 1, 7\) thì \(D\) cần tìm là \(6\) với \(i = 2\) và \(j = 4\).

Yêu cầu: Cho dãy số nguyên \(a_1, a_2, ..., a_n\). Hãy tìm giá trị cách chọn tối ưu.

Input

Dữ liệu vào từ tệp văn bản BAI1.INP:

• Dòng đầu chứa số nguyên dương \(n\) (\(2 \le n \le 10^6\));
• Dòng thứ hai chứa n số nguyên \(a_1, a_2, ..., a_n\) (\(|ai| \le 10^6\)).

Output

Kết quả ra tệp văn bản BAI1.OUT:

• Giá trị của cách chọn tối ưu.

Examples

6
4 2 5 8 1 7

6

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2013 - 2014

Cho một bảng \(A\) kích thước \(m \times n\) được chia thành các ô vuông đơn vị. Các hàng được đánh số từ \(1\) tới \(m\) từ trên xuống dưới. Trên mỗi hàng, các ô được đánh số theo thứ tự từ \(1\) tới \(n\) từ trái qua phải. Một số ô vuông được tô một trong các màu xanh (kí hiệu \(X\)), đỏ (kí hiệu \(D\)) hoặc vàng (kí hiệu \(V\)), một số ô không tô màu (kí hiệu \(T\)). Người ta dán mép trái và mép phải của bảng sao cho ô \((i, 1)\) và ô \((i, n)\) liền kề nhau (với mọi \(i\): \(1 \le i \le n\)).

Yêu cầu: Cho phép các ô chưa tô màu \((T)\) được tô một màu bất kỳ trong các màu \(X, D\) hoặc \(V\). Hãy chọn cách tô màu các ô chưa tô màu \((T)\) sao cho số lượng các ô liên tục cùng màu trên một hàng nào đó là nhiều nhất. Giả thiết rằng trên bảng đã cho, mỗi hàng đều có ít nhất một ô đã được tô.

Ví dụ: Với \(m = 4\), \(n = 6\). Một cách tô màu bảng A như sau:

Ta tô ở hàng \(2\) tất cả các ô chưa tô màu \((T)\) thành màu xanh \((X)\). Khi đó hàng \(2\) có nhiều nhất các ô liên tục cùng màu xanh đó là các ô \((2, 5), (2, 6), (2,1), (2, 2), (2, 3).\)

Input

Dữ liệu vào từ tệp văn bản BAI2.INP:

• Dòng đầu \(2\) số nguyên dương \(m , n\) (\(1 \le m \le 200, 1 \le n \le 200\))
• \(M\) dòng tiếp theo, mỗi dòng gồm các ký tự thuộc \({X, D, V, T}\), các ký tự cách nhau một dấu cách.

Output

Kết quả ra tệp văn bản BAI2.OUT:

• Dòng đầu ghi số ô liên tục nhiều nhất cùng màu của một hàng.
• Dòng thứ hai ghi chỉ số hàng của bảng và màu tương ứng. Nếu có nhiều hàng cùng thỏa mãn điều kiện thì ghi ra hàng có chỉ số nhỏ nhất, và trên dòng đó có hơn một màu thoả mãn thì ghi ra màu có thứ tự từ điển nhỏ nhất.

Examples

4 6
D D X X T T
T T X D X T
X D X D X D
D D X V T T

5
2 X

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2013 - 2014

Cho số nguyên \(n\), và \(n\) đoạn số nguyên \([a_i, b_i]\) (\(1 \le i \le n\)). Độ dài đoạn số nguyên \([a_i, b_i]\) là \(b_i - a_i\). Đoạn \([a_{i1}, b_{i1}]\) được gọi là đoạn con của đoạn \([a_i, b_i]\) nếu \(a_{i1}, b_{i1}\) là các số nguyên và \(a_i \le a_{i1} < b_{i1} ≤ b_i\). Chia các đoạn đã cho thành các đoạn con sao cho có được \(k\) đoạn con có độ dài bằng nhau. (Có thể không cần chia hết các đoạn).

Ví dụ: Với \(n = 6, k = 8\)

Với \(5\) đoạn thẳng là: \(A = [1, 10], B = [1, 6], C = [2, 8], D = [6, 9], E = [7, 11], F = [2, 4]\) thì ta chia như sau:

• \(A\) thành \(A_1 = [1, 4], A_2 = [4, 7], A_3 = [7, 10]\);
• \(B\) thành \(B_1 = [1, 4], B_2 = [4, 6]\);
• \(C\) thành \(C_1 = [2, 5], C_2 = [5, 8]\);
• \(D\) thành \(D_1 = [6, 9]\) (chỉ chia thành \(1\) đoạn);
• \(E\) thành \(E_1 = [7, 10], E2 = [10, 11]\);
• \(F\) không chia.

Như vậy \(8\) đoạn nhận được có cùng độ dài \(3\) sau khi chia là \(A_1, A_2, A_3, B_1, C_1, C_2, D_1, E_1\).

Yêu cầu: Xác định độ dài lớn nhất của đoạn con có thể nhận được. Dữ liệu vào luôn đảm bảo có cách chia.

Input

Dữ liệu vào từ tệp văn bản BAI3.INP:

• Dòng đầu tiên chứa hai số nguyên \(n, k\) (\(1 \le n \le 10^5, 1 \le k \le 10^5\)).
• Dòng thứ \(i\) trong \(n\) dòng sau mỗi dòng chứa hai số nguyên \(a_i, b_i\) (\(1 \le i \le n, 1 \le a_i < b_i \le 10^9\)).

Output

Kết quả ra tệp văn bản BAI3.OUT:

• Độ dài lớn nhất tìm được.

Examples

6 8
1 10
1 6
2 8
6 9
7 11
2 4

3