An và Bình là hai anh em.


Ba của An sau một chuyến đi công tác xa nhà trở về, mua cho An và Bình \(N\) gói kẹo, gói thứ \(i\) có \(A_i\) viên kẹo.


Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:


- Trước hết, ba của An chọn ra một số nguyên \(k\) (với \(1 \leq k \leq N\))


- An sẽ được chia các gói kẹo từ \(1\) đến \(k\). Phần còn lại (các gói kẹo từ \(k + 1\) đến \(N\)) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số \(k\) sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Input

• Dòng đầu tiên gồm số nguyên \(N (2 \leq N \leq 200000)\) - số gói kẹo.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N (1 \leq A_i \leq 10^9)\) - số viên kẹo trong từng gói kẹo.

Output

• In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 2000\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

5
5 1 3 2 6

1

6
4 5 3 6 1 2

3

2
100 100

0

Nguồn: Free Contest

Cho biết danh sách phát của một đài phát thanh kể từ khi thành lập. Danh sách phát có tổng cộng \(n\) bài hát.

Dãy các bài hát liên tiếp dài nhất, mà mỗi bài trong đó đều độc nhất là dãy nào?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng bài hát.
• Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): mã số của mỗi bài hát.

Output

• In độ dài của dãy dài nhất mà mỗi bài hát là duy nhất.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le k_i \le 10^9\)

Example

Sample input

8
1 2 1 3 2 7 4 2

Sample output

5

Bước vào tiểu học, Bé Bi được cô giáo chủ nhiệm cho làm lớp trưởng. Nhân dịp kỷ niệm ngày thành lập trường, Bé Bi tổ chức cho cả lớp chơi 1 trò chơi sau:
Có \(N\) đống sỏi xếp thành một hàng, đống thứ \(i\) có \(A_i\) viên sỏi. Ta có thể ghép hai đống sỏi bất kỳ thành một đống và mất một chi phí bằng 5% tổng hai đống sỏi đó. Hãy tìm cách ghép \(N\) đống sỏi này thành một đống với chi phí là nhỏ nhất.
Ví dụ: Nếu chúng ta có 4 đống sỏi với số lượng sỏi là 10, 11, 12 và 13.

• Bước 1: Ghép 2 đống 10 và 11 thành 1 đống có số lượng 21 (chi phí là \(1.05\))
• Bước 2: Ghép đống 21 vừa thu được với đống 12 thành đống có số lượng 33 (chi phí \(1.65\))
• Bước 3: Ghép đống 33 vừa thu được với đống 13 thành 1 đống cuối cùng có số lượng sỏi là 46 (chi phí \(2.3\))
• Vậy tổng chi phí là \(5.00\). Tuy nhiên đây không phải là phương án ghép đống tối ưu, chúng ta có phương án ghép 4 đống này thành 1 đống với chi phí nhỏ nhất là \(4.60\).

Các bạn hãy tìm giúp Bé Bi phương án chơi tối ưu nhé!

Input

• Dòng 1: Số nguyên dương \(N\ (2≤N≤100.000)\) là số đống sỏi.
• Dòng tiếp theo, ghi \(N\) số nguyên dương, tương ứng là số lượng sỏi trong từng đống. Số lượng sỏi không vượt quá 10.000.

Output

• Đưa ra một số thực duy nhất là chi phí nhỏ nhất phải trả để ghép N đống sỏi thành 1 đống. Kết quả ghi dưới dạng 2 chữ số sau dấu thập phân.

Scoring

Example

4
10 11 12 13

4.60

2
1 1

0.10