GIAO LƯU LẦN 7

An và Bình là hai anh em. Ba của An sau 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 (1 ≤ k ≤ 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 ≤ N ≤ 200000)\) là số gói kẹo.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N (1 ≤ A_i ≤ 10^9)\) là 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ể.

5
5 1 3 2 6

1

6
4 5 3 6 1 2

3

2
100 100

0

Giải thích

• Trong ví dụ thứ nhất, nếu chọn k = 3 thì tổng số kẹo An được chia là 5 + 1 + 3 = 9, tổng số kẹo Bình được chia là 2 + 6 = 8, chênh lệch lượng kẹo là |9 − 8| = 1.
• Trong ví dụ thứ hai, có hai cách chọn k tối ưu:

• Chọn k = 2. Tổng số kẹo An được chia là 4 + 5 = 9, tổng số kẹo Bình được chia là 3 + 6 + 1 + 2 = 12, chênh lệch lượng kẹo là |9 − 12| = 3.
• Chọn k = 3. Tổng số kẹo An được chia là 4 + 5 + 3 = 12, tổng số kẹo Bình được chia là 6 + 1 + 2 = 9, chênh lệch lượng kẹo là |12 − 9| = 3.

Cho số nguyên dương \(X\). Hãy tìm số nguyên dương lớn nhất không vượt quá \(X\) có thể biểu diễn dưới dạng \(b^n\) với \(b\) và \(n\) là các số nguyên dương thoả \(b ≥ 1\) và \(n ≥ 2\)

Input

• Gồm một dòng duy nhất chứa một số nguyên dương \(X (1 ≤ X ≤ 10^5)\).

Ouput

• In ra số nguyên dương cần tìm

10

9

1000

1000

Chơi đá là một nghệ thuật, người chơi đá là một nghệ sĩ...
— FireGhost.

Alob và Bice là những người chơi đá giỏi nhất thế giới! Anh hùng thì trọng anh hùng, nhân dịp VNOI Cup, Alob và Bice đã hẹn gặp nhau ở vịnh Hạ Long để đàm đạo về đá học (stone-graphy).

Alob và Bice mỗi người sở hữu \(n\) viên đá, trên mỗi viên đá được viết một con số. Hai người sẽ xếp những viên đá của mình thành một dãy, với \(a_i\) là con số viết trên hòn đá thứ \(i\) của Alob, và \(b_j\) là con số viết trên hòn đá thứ \(j\) của Bice. Ta định nghĩa độ high của một cách sắp xếp là \(\sum\limits_{i = 1} ^{n} max(a_i,b_i)\).

Alob và Bice thống nhất rằng, họ muốn sắp xếp lại những viên đá của mình sao cho độ high đạt giá trị lớn nhất. Các bạn hãy giúp Alob và Bice nhé!

Input

• Mỗi input sẽ gồm nhiều test cases. Dòng đầu tiên của input gồm số nguyên dương \(t\) \((0 < t < 10^3)\) — số test cases của bài toán. Sau đây là mô tả của các test cases.
• Dòng đầu tiên của mỗi test case gồm số nguyên dương \(n\) \((0 < n < 10^5)\) — số viên đá mà Alob và Bice sở hữu.
• Dòng thứ hai của mỗi test case gồm \(n\) số nguyên dương \(a_1,a_2,..,a_n\) \((0 < a_i < 10^9)\) — những con số viết trên những viên đá của Alob.
• Dòng thứ ba của mỗi test case gồm \(n\) số nguyên dương \(b_1,b_2,..,b_n\) \((0 < b_i < 10^9)\) — những con số viết trên những viên đá của Bice.
• Dữ liệu đảm bảo tổng của \(n\) trong tất cả các test cases không vượt quá \(10^5\).

Output

• Với mỗi test case, in ra một số nguyên duy nhất — độ high lớn nhất có thể của một cách sắp xếp các viên đá.

2
3
1 4 3
3 5 2
2
4 5
7 9

12
16

Notes

• Ở test case đầu tiên, ta có thể sắp xếp lại những viên đá của Alob thành\([3,1,4]\) và sắp xếp lại những viên đá của Bice thành \([3,5,2]\) khi có độ high của cách sắp xếp này sẽ là: \(max(3,3) + max(1,5) + max(4,2) = 3 + 5 + 4 = 12\)
• Ở test case thứ hai, ta có thể sắp xếp lại những viên đá của Alob thành \([5,4]\) và sắp xếp ại những viên đá của Bice thành \([9,7]\) khi đó có độ high của cách sắp xếp này sẽ là: \(max(5,9) + max(4,7) = 9 + 7 = 16\)

Cho một dãy số nguyên \(A\) gồm \(N\) phần tử. 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\).
Hãy xóa 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

• Dòng đầu tiên gồm số nguyên \(N\) \((3 ≤ N ≤ 1000)\) - số phần tử trong dãy.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, . . . , A_n (1 ≤ A_i ≤ 10^9)\) - số phần tử trong dãy.

Output

• In ra độ đẹp lớn nhất của dãy a sau khi xóa đi một phần tử bất kì

4
2 4 5 6

3

5
1 2 2 3 4

2

5
1 1 1 1 1

0

Giải thích

• Với ví dụ thứ nhất, ta sẽ xóa đi phần tử thứ \(2\) trong dãy \(A\). Dãy sau khi xóa là \([2, 5, 6]\) và có
  độ đẹp là \(3\).
• Với ví dụ thứ hai, ta sẽ xóa đi phần tử thứ \(4\) trong dãy \(A\). Dãy sau khi xóa là \([1, 2, 2, 4]\) và
  có độ đẹp là \(2\).
• Với ví dụ thứ ba, dù xóa đi phần tử nào thì độ đẹp của dãy thu được cũng đều bằng \(0\).