Cho một số nguyên dương \(n\), một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\) và một số thực \(x\).
Hãy tìm phần tử trong dãy \(a\) có giá trị gần với \(x\) nhất.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{3}\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, a_3, \dots, a_n\) (\(1 \le a_i \le 10^{3}\)).
• Dòng thứ ba gồm một số thực \(x\) (\(0 \le x \le 10^{3}\)).

Output

• In ra giá trị của phần tử gần với \(x\) nhất trong dãy \(a\). Nếu có nhiều phần tử thỏa mãn, in ra giá trị của phần tử có vị trí nhỏ nhất.

Examples

5
1 2 4 3 5
3.6

4

Cho một số nguyên dương \(N\), một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\).
Hãy tìm phần tử trong dãy \(a\) có giá trị gần với trung bình cộng các phần tử trong dãy \(a\) nhất.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{3}\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, a_3, \dots, a_n\) (\(1 \le a_i \le 10^{3}\)).

Output

• In ra giá trị của phần tử gần với trung bình cộng các phần tử trong dãy \(a\) nhất. Nếu có nhiều phần tử thỏa mãn, in ra giá trị của phần tử có vị trí nhỏ nhất.

Examples

5
1 -3 7 2 9

2

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). Hãy thay đổi từng phần tử trong dãy \(a\) qua phép biến đổi sau: Thay \(a_i\) bằng số 1 nếu \(a_i\) dương, thay \(a_i\) bằng \(-1\) nếu \(a_i\) âm, giữ nguyên \(a_i\) nếu \(a_i = 0\).

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 10^{5}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• In ra các phần tử của dãy \(a\) sau khi biến đổi lần lượt trên một dòng. Các phần tử cách nhau ít nhất một khoảng trắng.

Examples

6
0 1 2 3 -4 -5

0 1 1 1 -1 -1

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). Hãy đổi chỗ phần tử đầu tiên và phần tử cuối cùng của dãy \(a\).

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 10^{5}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• In ra các phần tử của dãy \(a\) sau khi đổi chỗ các phần tử lần lượt trên một dòng. Các số cách nhau ít nhất một khoảng trắng.

Examples

5
1 2 3 4 5

5 2 3 4 1

Một dãy được gọi là đối xứng nếu dãy không thay đổi khi đọc từ trái qua phải hay đọc từ phải qua trái. Cụ thể dãy \(b\) gồm \(n\) phần tử \(b_1, b_2, b_3, \ldots, b_n\) là dãy đối xứng khi \(b_1 = b_n,\; b_2 = b_{n-1},\; b_3 = b_{n-2},\ldots\)

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). Hãy kiểm tra xem dãy \(a\) có đối xứng hay không.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• In ra YES nếu dãy \(a\) là dãy đối xứng, ngược lại in ra NO.

Examples

5
1 6 2 6 1

YES

Cho một số nguyên dương \(n\) cùng hai dãy \(a, b\) lần lượt gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\) và \(b_1, b_2, b_3, \ldots, b_n\).
Hãy xây dựng dãy \(c\) gồm các khoảng cách giữa các phần tử trong hai dãy \(a\) và \(b\). Cụ thể, dãy \(c\) gồm \(n\) phần tử sao cho:

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{5}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)).
• Dòng thứ ba gồm \(n\) số nguyên \(b_1, b_2, b_3, \ldots, b_n\) (\(1 \le b_i \le 10^{9}\)).

Output

• In ra các phần tử của dãy \(c\) lần lượt trên một dòng. Các phần tử cách nhau ít nhất một khoảng trắng.

Examples

6
3 5 6 7 8 1
2 7 8 1 6 2

1 2 2 6 2 1

Cho số nguyên dương \(n\) là kích thước của hai mảng số nguyên \(a\) và \(b\).

Hãy tính tổng \(a_i + b_i\) lớn nhất với \(1 \le i \le n\).

Đầu vào

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((|a_i| \leq 10^9)\).
• Dòng thứ ba chứa \(n\) số nguyên \(b_i\) \((|b_i| \leq 10^9)\).

Đầu ra

• Ghi ra màn hình theo yêu cầu đề bài.

Ví dụ

6
3 5 6 7 8 1
2 7 8 1 6 2

14

Cho một số nguyên dương \(x\). Hãy tìm số Fibonacci lớn nhất không vượt quá \(x\), biết rằng số Fibonacci là số có dạng:

\(F_1 = 1\)

\(F_2 = 1\)

\(F_3 = F_1 + F_2\)

\(...\)

\(F_n = F_{n-1} + F_{n-2}\)

Đầu vào

• Dòng duy nhất chứa số nguyên dương \( x \) \((1 \le x \le 10^9\)).

Đầu ra

• Ghi ra màn hình số nguyên Fibonacci lớn nhất không vượt quá \(x\).

Ví dụ

9

8

Nhập vào dãy \(A\) có \(n\) phần tử. Tính đoạn con dài nhất chứa các phần tử dương của dãy \(A\).

Input

• Số nguyên dương \(n\) \((1 \leq n \leq 1000)\).
• Các số nguyên \(a_i(i = 1..n)\) \((-10^6 \leq a_i \leq 10^6)\).

Output

• In ra độ dài của đoạn con tìm được.

Example

9
1 2 2 2 -2 3 -4 3 4 

4

Nhập vào dãy \(A\) có \(n\) phần tử. Tính đoạn con dài nhất chứa các phần tử tăng hoặc giảm dần trong dãy \(A\)

Input

• Số nguyên dương \(n\) \((1 \leq n \leq 1000)\)
• Các số nguyên \(a_i(i = 1..n)\) \((-10^6 \leq a_i \leq 10^6)\)

Output

• In ra độ dài của đoạn con tìm được

Example

9
1 2 2 2 -2 -2 2 3 5

4