Cho một dãy số nguyên ~a~ gồm ~n~ phần tử. Tập điểm ~S~ trên hệ trục tọa độ ~Oxy~ sẽ được xây dựng từ dãy ~a~, cụ thể hơn, nó bao gồm các điểm có tọa độ ~(a_i,a_j)~, ~\forall 1 \le i < j \le n~.

Gọi bao lồi của tập điểm ~S~ là ~C~, ~Area(C)~ là diện tích của ~C~, hãy tính ~2*Area(C)~.

Input

• Dòng đầu gồm số nguyên dương ~n~ là độ dài dãy ~a~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~.

  Output

• In ra ~2*Area(C)~, có thể chứng minh rằng đây là một số nguyên.

Constraints

• ~3 \le n \le 10^5~.
• ~1 \le a_i \le 10^8~.

Subtask

• ~50\%~ số điểm có ~n \le 1000~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

4
2 4 1 3

Sample Output 1

13

Explanation 1

Đa giác ~DCFEA~ chính là bao lồi của tập điểm và ~2*Area(C) = 2*6.5 = 13~

Hôm nay là sinh nhật ~ABC~ và ~DEF~ muốn chuẩn bị một chiếc bánh cho cô ấy. Anh ấy có ~n~ điểm ~(x_1, y_1), (x_2, y_2), …, (x_n, y_n)~ trong mặt phẳng hai chiều, và một cây nến được đặt ở một điểm trong mặt phẳng.

Số lớp của chiếc bánh là một số không âm. ~DEF~ coi độ ngon của chiếc bánh bằng với số lớp của chiếc bánh. Một lớp là một đa giác đơn với các đỉnh là một số điểm trong ~n~ điểm của ~DEF~. Với mỗi điểm của ~DEF~, nó không nhất thiết phải thuộc một lớp. Hơn nữa các lớp phải thỏa mãn các điều kiện sau:

• Với mỗi lớp, cây nến phải nằm hẳn bên trong nó
• Với mỗi điểm trong ~n~ điểm mà nằm hẳn trong một lớp, nó phải thuộc lớp khác hoặc có thể là điểm của cây nến
• Không có hai lớp nào chạm hoặc giao nhau
• Các lớp phải được chọn sao cho độ ngon của chiếc bánh là lớn nhất có thể

Bây giờ ~DEF~ tự hỏi, độ ngon của chiếc bánh phụ thuộc thế nào vào vị trí đặt nến. Bạn cần trả lời ~q~ truy vấn. Trong mỗi truy vấn, bạn được cho một điểm ~p = (x, y)~ là điểm mà ~DEF~ đặt nến và bạn cần tìm phải độ ngon của chiếc bánh

Input

• Dòng đầu gồm số nguyên dương ~n~ và ~q~.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i,y_i~.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x,y~ miêu tả truy vấn.

  Output

• Với mỗi truy vấn, in ra một dòng chứa số nguyên là độ ngon của bánh.

Constraints

• ~3 \le n \le 5000~.
• ~1 \le q \le 2000~.
• ~-10^9 \le x_i,y_i \le 10^9~.
• ~-10^9 \le x,y \le 10^9~.

Subtask

• ~50\%~ số điểm có ~1 \le n,q \le 200~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

6 2
0 0
6 0
3 4
2 1
4 1
3 3
6 6
3 3

Sample Output 1

0
1

Explanation 1

Trong truy vấn đầu tiên, ~p = (6, 6)~. Bánh không thể có lớp nào, nên độ ngon của nó là ~0~

Trong truy vấn thứ hai, ~p = (3, 3)~. Bánh chỉ có thể có một lớp, ví dụ là một tam giác với các đỉnh là ~(2, 1), (4, 1), (3, 4)~. Có những lựa chọn khác cho lớp này nhưng bánh không thể có nhiều hơn ~1~ lớp.

Tay săn ảnh trẻ tuổi nhưng đầy triển vọng ABC rất muốn trở nên nổi tiếng. Để làm được điều này, anh ấy muốn chụp ảnh một siêu sao mới nổi trong khi cô ấy đi dạo trên núi.

Được biết, quãng đường của ngôi sao đó trên núi gồm ~n~ đoạn. Với mỗi ~i~, đoạn đường thứ ~i~ là một khoảng nửa mở thẳng đứng có tọa độ ~x = i~ và ~y ∈ [0, hi)~.

Nếu ABC đứng ở vị trí ~j~ và người nổi tiếng ấy đứng ở vị trí ~i~, anh ta có thể chụp được cô khi và chỉ khi anh ta nhìn thấy cô, tức là ~i < j~ và với mọi ~i < k < j~, khoảng nửa mở tạo lên đoạn thứ ~k~ không được cắt đoạn ~[(i,j_i),(j,h_j)]~. ABC là một tay săn ảnh, dĩ nhiên không phải là một lập trình viên, vì vậy anh muốn bạn xác định khoảng cách tối đa mà anh ấy có thể chụp được ảnh ngôi sao nổi tiếng trên, tức là tìm là giá trị lớn nhất của ~j - i~ trên tất cả các cặp ~(i, j)~ thỏa mãn điều kiện. Hãy giúp anh ấy trở nên nổi tiếng!

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng đoạn.
• Dòng thứ hai gồm ~n~ số nguyên ~h_1,h_2,...,h_n~.

Output

• In ra khoảng cách lớn nhất cần tìm.

Constraints

• ~3 \le n \le 10^5~.
• ~1 \le h_i \le 10^9~.

Subtask

• ~50\%~ số điểm có ~n \le 1000~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

7
3 2 5 3 2 4 3

Sample Output 1

3

Explanation 1

Cặp ~(3,7)~ không thỏa mãn do ~FN~ giao với ~KL~. Cặp ~(3,6)~ là một cặp thỏa mãn và cho ra kết quả tốt nhất.

Trên hệ trục tọa độ vuông góc ~Oxy~, cho tọa độ ~N~ điểm trong đó không có ba điểm nào thẳng hàng.

Yêu cầu: Tìm hai điểm trong ~N~ điểm để đường thẳng chứa hai điểm đó chia ~N-2~ điểm còn lại thành hai phần sao cho tổng số điểm của mỗi phần chênh lệnh nhau không quá ~1~.

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

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 10^5)~ là số lượng điểm;
• ~N~ dòng sau, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của một điểm ~(|x| ≤ 10^9~; ~\ |y| ≤ 10^9)~.

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

Một dòng gồm bốn số nguyên là toạ độ của hai điểm thoả mãn. Có thể có nhiều kết quả, ghi ra một kết quả bất kì.

Ràng buộc

• Có ~30\%~ số test ứng với ~N ≤ 100~;
• ~30\%~ số test khác ứng với ~N ≤ 5000~;
• ~40\%~ số test còn lại ứng với ~N ≤ 10^5~.

Ví dụ

Input

4
0 0
0 1
1 1
1 0

Output

0 0 1 1

Cho dãy ~a~ nguyên dương gồm ~n~ phần tử.

Bạn có thể thực hiện thao tác sau vô số lần:

• Chọn ra một đoạn ~[l,r]~ ~(1 \le l \le r \le n)~ và thay thế ~a_l = a_{l+1} = ... = a_r = \frac{a_l+a_{l+1}+...+a_r}{r-l+1}~. Ví dụ, nếu có dãy ~a = [1,3,6,7]~ và bạn chọn đoạn ~[2,3]~, ta sẽ thu được dãy ~a = [1,4.5,4.5,7]~.

Hãy in ra dãy ~a~ có thứ tự từ điển nhỏ nhất mà bạn có thể thu về được.

Dãy ~a~ có thứ tự từ điển bé hơn dãy ~b~ có cùng độ dài khi: gọi vị trí ~i~ là vị trí đầu tiên mà ~a~ và ~b~ khác nhau, ta có ~a_i < b_i~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra giá trị ~a_i~ của dãy ~a~ tốt nhất tìm được. Kết quả lấy ~9~ chữ số sau dấu phẩy.

Constraints .

• ~1 \le n \le 2\times10^5~
• ~1 \le a_i \le 10^6~

Subtask

• Sub ~1~ (~30\%~): ~n \le 20~.
• Sub ~2~ (~30\%~): ~n \le 2000~.
• Sub ~3~ (~40\%~): ~n \le 2\times10^5~.

  Sample Input 1

5
1 3 2 2 3

Sample Output 1

1.000000000
2.333333333
2.333333333
2.333333333
3.000000000

Explanation 1

Thực hiện ~1~ thao tác trên đoạn ~[2,3]~.

Các bé học sinh trường mầm non SuperKids tỏ ra say mê với các trò chơi đòi hỏi tư duy thuật toán chuyên nghiệp.

Nhân dịp đến thăm trường, giáo sư X bày ra một trò chơi cho các bạn nhỏ tại đây.

Ban đầu, người chơi được cho 𝑛 thùng nước đánh số từ ~1~ tới ~n~. Thùng thứ ~i~ có ~a_i~ lít nước. Người chơi được quyền múc một lượng nước bất kỳ từ một thùng chuyển sang thùng liền sau (chuyển từ thùng ~i~ sang thùng ~i + 1~ với ~i~ tùy chọn thỏa mãn ~1 \le i < n~). Năng lượng tiêu tốn cho thao tác này đúng bằng lượng nước được chuyển (có thể không phải là số nguyên)

Nhiệm vụ của người chơi là phải làm cho lượng nước trong các thùng sắp xếp thứ tự không giảm, tức là:

• ~a_1 \le a_2 \le ... \le a_n~

Yêu cầu: Hãy tìm phương án chơi sao cho tổng năng lượng tiêu tốn là ít nhất

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• In ra một số thực duy nhất với ~1~ chữ số sau dấu chấm thập phân là tổng năng lượng tiêu tốn nếu các bé chơi theo phương án của bạn.

Constraints .

• ~1 \le n \le 10^6~
• ~1 \le a_i \le 10^6~

Sample Input 1

6
1 3 0 0 3 0

Sample Output 1

4.5

Explanation 1

Ta sẽ chuyển nước để được lượng nước trong các thùng là ~1.0,1.0,1.0,1.0,1.5,1.5~

Chuyển ~2~ lít từ thùng ~2~ sang thùng ~3~

Chuyển ~1~ lít từ thùng ~3~ sang thùng ~4~

Chuyển ~1.5~ lít từ thùng ~5~ sang thùng ~6~