Cho số nguyên dương \(n\) . Hãy tính tổng \(S = - 1 + 2 - 3 + ... + n.(-1)^{n}\)

Input

• Một dòng duy nhất chứa số nguyên \(n\) (\(1 \leq n \leq 10^{12}\)).

Output

• Gồm một dòng duy nhất là kết quả tìm được.

Scoring

• Có 75% số test tương ứng với 75% số điểm của câu có \(n \leq 10^6\) ;
• Có 25% số test tương ứng với 25% số điểm của câu có \(n \leq 10^{12}\) .

Example

4

2

Số tự nhiên \(a\) chia hết cho tự nhiên \(x\) thì \(x\) được gọi là ước của \(a\). Nếu \(x < a\) thì được gọi là ước thực sự của \(a\).

Cho số tự nhiên \(n\) (\(1 \leq n \leq 10^6\)). Tìm số tự nhiên nhỏ hơn \(n\) có nhiều ước thực sự nhất.

Input

• Một dòng duy nhất chứa số nguyên \(n\) (\(1 \leq n \leq 10^{6}\)).

Output

• Gồm một dòng duy nhất là kết quả tìm được. Nếu có nhiều số thỏa mãn bài toán thì in ra số bé nhất trong số chúng.

Scoring

• Có 50% số test tương ứng với 50% số điểm của câu có \(n \leq 10^4\) ;
• Có 50% số test tương ứng với 50% số điểm của câu có \(n \leq 10^{6}\) .

Example

7

6

Số chính phương là số tự nhiên mà có thể viết dưới dạng bình phương của một số tự nhiên khác. Ví dụ: 0, 1, 4, 9, 16, 25, … là các số chính phương, còn các số 2, 3, 5, … không là số chính phương.

Cho dãy gồm \(n\) số nguyên \(a_1, a_2, a_3, ..., a_n\) . Tìm số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(0 \leq a_i \leq 10^{12}, i = 1, 2, ..., n\)), các số cách nhau một dấu cách.

Output

• Gồm một dòng duy nhất là kết quả tìm được.

Scoring

• Có 50% số test tương ứng với 50% số điểm của câu có \(1 \leq n \leq 10^3, 0 \leq a_i \leq 10^4\) ;
• Có 30% số test tương ứng với 30% số điểm của câu có \(10^3 \leq n \leq 10^6, 0 \leq a_i \leq 10^6\) ;
• Có 20% số test tương ứng với 20% số điểm của câu có \(0 \leq a_i \leq 10^{12}\).

Example

8
0 3 4 2 1 4 16 25

9

Nhân dịp năm mới, để thu hút khách hàng đến mua sắm, siêu thị Hùng Vương tổ chức chương trình khách hàng may mắn: mỗi khách hàng đến siêu thị đều nhận được một số may mắn, khách hàng thứ \(i\) nhận số may mắn là số nguyên \(a_i\) được tạo tự động bằng máy tính. Kết thúc chương trình có \(n\) khách hàng nhận được số may mắn. Ban tổ chức tiến hành quay số trúng thưởng, những khách hàng may mắn sẽ nhận được phần thưởng của siêu thị. Để đảm bảo tính khách quan Ban tổ chức nhờ một khách hàng bắt thăm ngẫu nhiên hai số nguyên \(x, y\) (\(1 \leq x, y \leq n\)) sau đó sử dụng chương trình máy tính để tìm ra hai số \(u, v\) (\(0 < u \leq v \leq 10^6\)) thỏa mãn các điều kiện sau:

• Số lượng người có số may mắn \(a_j\) thỏa mãn \(u \leq a_j \leq v\) tối thiểu là \(x\).
• Số lượng người có số may mắn \(a_j\) thỏa mãn \(u \leq -a_j \leq v\) tối thiểu là \(y\).
• Hiệu \(u - v\) nhỏ nhất.

Sau khi tìm được hai số \(u, v\) thỏa mãn các điều kiện trên khách hàng có số may mắn \(a_i\) thỏa mãn \(u \leq |a_i| \leq v\) sẽ được nhận phần thưởng của siêu thị.

Hãy giúp Ban tổ chức tìm hai số \(u, v\) thỏa mãn các điều kiện trên.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, x, y\) (\(1 \leq n \leq 2.10^5; x, y \leq n\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(0 < |a_1| < |a_2| < |a_3| < ... < |a_n| < 10^6\)).

Output

• Gồm một dòng duy nhất là hai số \(u, v\) tìm được (các số cách nhau một dấu cách). Nếu có nhiều cặp số (\(u, v\)) thỏa mãn bài toán thì in ra cặp số (\(u, v\)) có \(u\) nhỏ nhất; nếu không tìm được \(u, v\) thỏa mãn yêu cầu thì in ra -1.

Scoring

• Có 50% số test tương ứng 50% số điểm của bài có \(n \leq 2.10^2, |a_i| \leq 10^2\) ;
• Có 30% số test tương ứng 30% số điểm của bài có \(2.10^2 < n \leq 10^3, |a_i| \leq 10^4\) ;
• Có 30% số test tương ứng 30% số điểm của bài có \(2.10^3 < n \leq 10^5, |a_i| \leq 10^6\) ;

Example

4 1 2
1 -2 -3 4

1 3