Test thi thử HSG9

Hôm nay, các bạn nhỏ ABC Smart lại được Thầy giáo đố một bài toán sau: Cho một dãy số nguyên \(a_1, a_2,..., a_n\). Các phần tử trong dãy được sắp xếp theo trình tự tăng dần, tức là \(a_i ≤ a_{i+1}\) với mọi \(1 ≤ i < n\). Ta định nghĩa độ đẹp của dãy \(a\) là khoảng cách lớn nhất giữa hai phần tử liên tiếp bất kì trong dãy. Nói cách khác, độ đẹp của dãy \(a\) là giá trị \(a_i – a_{i-1}\) lớn nhất với mọi \(2 ≤ i ≤ n\).

Yêu cầu: Hãy xoá một phần tử bất kì trong dãy \(a\) sao cho độ đẹp của dãy nhận được là lớn nhất có thể.

Input

Vào từ file BAI2.INP gồm:

• Dòng đầu tiên là số nguyên dương \(n\) (\(3 ≤ n ≤ 10^6\));
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2,..., a_n (|a_i| ≤ 2.10^9)\).

Output

Ghi ra file BAI2.OUT một số nguyên là độ đẹp của dãy sau khi đã xoá 1 phần tử.

Example

4
2 4 5 6

3

Long là một học sinh chuyên Toán nhưng lại rất đam mê lập trình. Trong một lần Long được học về phép chia có dư đối với các số tự nhiên như sau: Nếu số tự nhiên \(N\) chia \(X\) dư \(R\) thì số \(N\) sẽ được biểu diễn thành dạng sau: \(N = K \times X + R\). Tình cờ được biết sắp tới ở trường chuyên Lam Sơn có tổ chức thi khảo sát chất lượng học sinh giỏi cấp 2, nên Long có bài toán đố các bạn như sau: Cho một số tự nhiên \(N\). Tìm số tự nhiên \(X < N\) sao cho kết quả của phép chia lấy dư \(N\) cho \(X\) là lớn nhất. Vì các bạn lập trình nên sẽ trả lời rất nhanh nên Long sẽ đưa ra \(T\) câu hỏi liên tục để các bạn trả lời.

Input

Vào từ file BAI3.INP gồm

• Dòng đầu tiên chứa số nguyên dương \(T\) là số lượng câu hỏi mà Long đưa ra ( \(T ≤ 10^5\));
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\) là một câu hỏi của Long (\(5 ≤ N ≤ 10^{18}\)).

Output

Ghi ra file BAI3.OUT gồm \(T\) dòng là các đáp án tương ứng..

Scoring

• Có 20% số điểm tương ứng với \(T ≤ 10^3\) và \(N ≤ 10^4\);
• Có 80% số điểm còn lại không có ràng buộc gì thêm.

Example

2
6
9

4
5

Hôm nay Long lại được học về xâu. Người ta định nghĩa một xâu đẹp là xâu chỉ chứa các ký tự là chữ cái nguyên âm. Theo quy ước thì các chữ cái là nguyên âm: ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ . Long liền nghĩ ra một bài toán để đố các bạn như sau: Cho xâu ST chỉ gồm các chữ cái in thường từ ‘a’ đến ‘z’. Tìm độ dài lớn nhất xâu con của xâu ST trên là xâu đẹp. Ta định nghĩa xâu con của xâu ST là xâu có các ký tự ở vị trí liên tiếp trong xâu ST và độ dài của một xâu là số ký tự của xâu đó.

Input

Vào từ file BAI4.INP gồm

• Dòng đầu tiên là số nguyên dương \(n\), \(n\) là độ dài xâu \(ST\ (1 \le n \le 10^5)\);
• Dòng thứ hai là xâu \(ST\).

Output

Ghi ra file BAI4.OUT một số nguyên là kết quả của bài toán. Nếu không có xâu con nào thoả mãn thì ghi ra số -1.

Scoring

• Có 20% số điểm tương ứng với \(N ≤ 100\);
• Có 80% số điểm còn lại không có ràng buộc gì thêm.

Example

11
ioiabcsmart

4