Một dãy ~a_1, a_2, \dots, a_n~ được gọi là cân bằng nếu có thể chia dãy thành hai đoạn liên tiếp có tổng bằng nhau, tức là tồn tại một vị trí ~p~ (~1 \leq p < n~) sao cho tổng giá trị của ~p~ phần tử đầu dùng bằng của ~(n - p)~ phần tử cuối: $$\sum_{i=1}^{p} a_i = \sum_{i=p+1}^{n} a_i$$

Cho một dãy ~a_1, a_2, \dots, a_n~ độ dài ~n~. Bạn có thể biến dổi dãy ~a_1, a_2, \dots, a_n~ bằng cách thực hiện thao tác sau số lần tùy ý. Mỗi lần thực hiện thao tác có thể tùy ý lựa chọn một trong hai hành động:

• Chọn một vị trí ~i~ (~1 \leq i \leq n~) và tăng ~a_i~ lên 1.

• Chọn một vị trí ~i~ (~1 \leq i \leq n~) mà ~a_i > 1~ và giảm ~a_i~ cho 1.

Hãy thực hiện thao tác trên ít lần nhất để làm cho dãy a cân bằng.

Input

Vào từ tệp BALANCE.INP gồm:

Dòng đầu tiên chứa số nguyên ~n~ (~2 \leq n \leq 2 \times 10^5~) là độ dài dãy ~a~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 20242024~).

Output

Ghi kết quả lên tệp BALANCE.OUT gồm:

Một số nguyên duy nhất là số lần ít nhất cần thực hiện thao tác.

Scoring

Sample Input 1

5
1 2 3 4 5

Sample Output 1

3

Sample Input 2

2
1 2

Sample Output 2

1

Notes

Ở ví dụ 1, ta thực hiện cộng ~a_2~ cho 1, trừ ~a_4~ và ~a_5~ cho 1. Sau 3 lần thực hiện thao tác, dãy ~a~ trở thành ~1, 3, 3, 3, 4~, và có vị trí ~p = 3~ thỏa mãn yêu cầu đề bài.

Trung thu sắp đến, Bờm quyết định trang trí khu du lịch của mình. Trước cửa khu du lịch, có một hàng gồm ~N~ cây, đánh số từ ~1~ đến ~N~ theo chiều từ trái sang phải, cây thứ ~i~ có độ cao ~h_i~. Bờm quyết định chọn một số cây để treo, mỗi cây một đèn lồng đỏ trên ngọn, sao cho khi nhìn từ ngoài vào, các đèn lồng tạo thành một chữ M.

Chữ M được định nghĩa như sau: đó là một dãy các cây, khi xét từ trái sang phải, có thể chia thành 3 phần, trong đó độ cao các cây trong đoạn đầu tiên tăng nghiêm ngặt, trong đoạn thứ hai giảm nghiêm ngặt, trong đoạn thứ ba tăng nghiêm ngặt và trong đoạn thứ tư giảm nghiêm ngặt.

Tức là, có một dãy các chỉ số: ~a_0 < a_1 < \ldots < a_i < b_1 < b_2 < \ldots < b_j < c_1~ ~< c_2 < \ldots < c_k < d_1 < d_2 < \ldots < d_l~ sao cho:

• Dãy ~h_{a_1}, h_{a_2}, \ldots, h_{a_i}~ là dãy tăng nghiêm ngặt với ~i \geq 2~.

• Dãy ~h_{a_i}, h_{b_1}, \ldots, h_{b_j}~ là dãy giảm nghiêm ngặt với ~j \geq 1~.

• Dãy ~h_{b_j}, h_{c_1}, \ldots, h_{c_k}~ là dãy tăng nghiêm ngặt với ~k \geq 1~.

• Dãy ~h_{c_k}, h_{d_1}, \ldots, h_{d_l}~ là dãy giảm nghiêm ngặt với ~l \geq 1~.

Độ hoành tráng của chữ M là số lượng đèn lồng tạo thành chữ M. Hãy tìm độ hoành tráng lớn nhất của một chữ M mà Bờm có thể tạo được.

Input

Dòng đầu tiên là một số nguyên dương ~N~ (~1 \le N \le 50000~) — số cây.

Dòng thứ hai là ~N~ số nguyên dương ~h_1, h_2, \ldots, h_N~ (~1 \le a_i \le 10^9~) — độ cao của các cây.

Output

Hãy tìm độ hoành tráng lớn nhất của một chữ M mà Bờm có thể tạo được.

Scoring

Sample Input 1

15
1 20 15 30 25 20 15 40 30 20 10 5 4 6 8

Sample Output 1

12

Notes

Các cây tạo thành hình chữ M có độ cao là: ~1~ ~20~ ~30~ ~25~ ~20~ ~15~ ~40~ ~30~ ~20~ ~10~ ~5~ ~4~. Độ hoành tráng là ~12~.

Bờm và Cuộc cùng chơi một trò chơi có dãy số như sau: Bờm viết liên tiếp một dãy số gồm ~n~ chữ số thập phân, tiếp theo Cuội tách dãy chữ số thành các nhóm chữ số để nhận được một dãy số. Sau đó cả hai bạn cùng tiến hành tìm dãy con tăng dài nhất từ dãy số mới nhận được.

Ví dụ: Bờm viết dãy chữ số thập phân 314159265358979, nếu Cuội tách dãy trên thành dãy số gồm ~6~ số: 3, 14, 159, 26, 53, 58979 thì cả hai bạn sẽ tìm được dãy con tăng dài nhất gồm ~5~ số là: 3, 14, 26, 53,

1. Nhưng nếu Cuội tách thành dãy số gồm ~10~ số: 3, 1, 4, 1, 5, 9, 26, 53, 58, 979 thì cả hai bạn sẽ tìm được dãy con tăng dài nhất gồm ~8~ số là: 3, 4, 5, 9, 26, 53, 58, 979.

Yêu cầu: Cho dãy chữ số thập phân mà Bờm viết, hỏi với cách chơi như trên thì hai bạn có thể tìm được dãy con tăng dài nhất tối đa là bao nhiêu phần tử.

Input

Từ tệp văn bản INCSEQ.INP có dạng:

• Dòng đầu tiên ghi số nguyên dương ~n~ (~1 \leq n \leq 1000~)

• Dòng thứ hai là một xâu gồm ~n~ chữ số thập phân.

Output

Từ tệp văn bản INCSEQ.OUT một số duy nhất là độ dài của dãy con tăng dài nhất tìm được

Sample Input 1

15
314159265358979

Sample Output 1

8

Sample Input 2

10
1230456789

Sample Output 2

9

Công ty có một hệ thống mạng nội bộ gồm ~n~ thiết bị và ~m~ dây nối giữa các cặp thiết bị. Các thiết bị được đánh số từ ~1~ đến ~n~. Các dây nối được đánh số từ ~1~ đến ~m~. Dây nối thứ ~i~ (~1 \leq i \leq m~) kết nối hai thiết bị ~X_i, Y_i~ và có độ trễ là ~W_i~. Đảm bảo không có hai dây nối nào kết nối cùng một cặp thiết bị và luôn tồn tại ít nhất một đường truyền giữa hai cặp đỉnh bất kì.

Gọi đường truyền giữa hai thiết bị ~X~ và ~Y~ là dãy các thiết bị ~(X = x_1, x_2, \ldots, x_k = Y)~ sao cho với mọi ~i~ (~1 \leq i < k~) thì có dây nối giữa hai đỉnh ~x_i~ và ~x_{i+1}~, và độ trễ của đường truyền trên là tổng độ trễ của các dây nối giữa các ~x_i~ và ~x_{i+1}~.

Gọi độ trễ giữa hai thiết bị ~X~ và ~Y~ là độ trễ bé nhất của đường truyền bất kì giữa hai thiết bị ~X~ và ~Y~.

Sắp tới bạn được giao nhiệm vụ cải tạo một trong những đường truyền có độ trễ bé nhất giữa hai thiết bị ~S~ và ~T~ (chọn đường truyền nhanh nhất để tiết kiệm chi phí).

Nếu bạn chọn cải tạo đường truyền ~(S = v_1, v_2, \ldots, v_k = T)~ thì với mọi ~i~ (~1 \leq i < k~), dây nối giữa các cặp thiết bị ~v_i~ và ~v_{i+1}~ sẽ được giảm độ trễ xuống bằng ~0~ (các dây nối thuộc đường truyền được cải tạo hầu như không còn độ trễ). Vì lí do riêng mà bạn muốn sau lần cải tạo này độ trễ giữa hai thiết bị ~U~ và ~V~ là bé nhất có thể.

Input

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

• Dòng đầu tiên chứa hai số nguyên ~n, m~ (~2 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5~) là số thiết bị và số dây nối

• Dòng thứ hai chứa hai số nguyên ~S, T~ (~1 \leq S, T \leq n, S \neq T~)

• Dòng thứ ba chứa hai số nguyên ~U, V~ (~1 \leq U, V \leq n, U \neq V~)

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~X_i, Y_i, W_i~ tương ứng với một dây nối giữa hai thiết bị ~X_i~ và ~Y_i~, dây nối thứ ~i~ có độ trễ là ~W_i~ (~1 \leq X_i < Y_i \leq n, 1 \leq W_i \leq 10^9~).

Output

Kết quả: ghi kết quả lên tệp PATH.OUT

• Một dòng duy nhất chứa một số nguyên, là độ trễ nhỏ nhất có thể giữa hai thiết bị ~U~ và ~V~ sau khi cải tạo các kết nối.

Scoring

Ràng buộc:

• Subtask 1: (16% số điểm) ~S = U~

• Subtask 2: (15% số điểm) có duy nhất một đường truyền có độ trễ nhỏ nhất giữa hai thiết bị ~S~ và ~T~

• Subtask 3: (24% số điểm) ~n \leq 300~

• Subtask 4: (45% số điểm) không có ràng buộc gì thêm

Sample Input 1

6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

Sample Output 1

2

Notes

Giải thích:

Lựa chọn cải tiến đường truyền: ~(1, 2, 3, 5, 6)~

Sau đó đường truyền có độ trễ nhỏ nhất giữa hai thiết bị 1 và 4 là ~(1, 2, 3, 5, 4)~. Trong đó độ trễ của dây nối giữa hai thiết bị 5 và 4 là 2, độ trễ của các dây nối còn lại trên đường truyền này đều là 0.

Bờm tham gia trò chơi rút thăm trúng thưởng trong đêm hội Trăng rằm. Ban tổ chức chuẩn bị ~k~ loại thẻ bài, các loại thẻ bài tương ứng ghi các giá trị từ ~1~ đến ~k~, các thẻ được sắp xếp vào trong 2 chiếc hộp như sau:

• Hộp thứ nhất: chỉ chứa các loại thẻ bài có giá trị là số lẻ trong đoạn từ ~1~ đến ~k~, số lượng mỗi loại thẻ không giới hạn.

• Hộp thứ hai: chỉ chứa các loại thẻ bài có giá trị là số chẵn trong đoạn từ ~1~ đến ~k~, số lượng mỗi loại thẻ không giới hạn.

Theo thể lệ của Ban tổ chức, một người chơi sẽ được thực hiện ~n~ lần rút thẻ. Các lượt rút thẻ theo thứ tự bắt đầu từ hộp thứ nhất tới hộp thứ hai và lặp lại quá trình đó.

Ví dụ: ~k = 4, n = 3~

• Lượt thứ nhất: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị ~1~ hoặc ~3~.

• Lượt thứ hai: Người chơi rút thẻ trong hộp thứ hai có thể nhận được các thẻ bài có giá trị ~2~ hoặc ~4~.

• Lượt thứ ba: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị ~1~ hoặc ~3~.

Ban tổ chức đưa ra một con số ~m~ và người chơi sẽ nhận được quà nếu tổng giá trị các thẻ bài sau ~n~ lần rút là một số chia hết cho ~m~.

Yêu cầu: Hãy tính giúp Bờm xem có bao nhiêu cách rút ra các thẻ bài để có thể nhận được thưởng.

Input

Vào từ tệp văn bản CARDS.INP

• Một dòng gồm ba số nguyên dương ~n, k, m~ (~2 \leq n, k \leq 10^9, m \leq 100~).

Output

Xuất ra tệp văn bản CARDS.OUT

• Một số nguyên dương là số cách rút thẻ thỏa mãn yêu cầu của Ban tổ chức. Vì kết quả rất lớn nên bạn chỉ cần đưa ra phần dư của đáp án khi chia cho ~123456789~.

Scoring

Sample Input 1

3 4 4

Sample Output 1

4

Sample Input 2

3 2 4

Sample Output 2

1

Thuật toán sắp xếp nổi bọt để sắp xếp không giảm một dãy số nguyên ~b~ độ dài ~m~, có thể được mô tả như sau:

• Bước 1: nếu dãy ~b~ là một dãy không giảm thì kết thúc thuật toán

• Bước 2: Chọn một vị trí ~i~ (~1 \le i < m~) nhỏ nhất mà ~b_i > b_{i + 1}~, tráo đổi giá trị của hai phần tử ~b_i~ và ~b_{i + 1}~. Tiếp tục quay lại Bước 1.

Cho một dãy số nguyên ~a~ độ dài ~n~, số thứ ~i~ là ~a_i~ (~|a_i| \le 10^9~). Đếm số cách chia dãy ~a~ thành các dãy đẹp liên tiếp, chia dư cho (~10^9 + 7~).

Một dãy liên tiếp được gọi là dãy đẹp nếu số bước để sắp xếp không giảm dãy đó bằng thuật toán sắp xếp nổi bọt nêu trên, sử dụng không qua ~k~ (~k \le n^3~) lần tráo đổi giá trị ở Bước 2.

Input

Vào từ tệp văn bản NARR.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~n \le 2 \times 10^5~, ~k \le n^3~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^9~), các số cách nhau bởi ít nhất một dấu cách.

Output

Ghi kết quả lên tệp văn bản NARR.OUT

• Gồm một số nguyên duy nhất là số cách chia dãy ~a~ thành các dãy đẹp liên tiếp thỏa mãn yêu cầu đề bài

Scoring

Sample Input 1

5 10
1 2 3 4 5

Sample Output 1

16

Sample Input 2

3 1
3 2 1

Sample Output 2

3

Sau khi thử nghiệm thành công với mô hình máy bơm nước để tưới tiêu, Giáo sư X dần mở rộng các thửa ruộng của mình thành mô hình trang trại. Tức là ngoài trồng cấy ông còn chuyển sang chăn nuôi. Trang trại của Giáo sư có một dãy căn phòng cũ dùng để làm chuồng cho các con bò mới mua. Các phòng được đánh số lần lượt từ ~1, 2,...~ Cụ thể, phòng ~i~ và ~i + 1~ là hai phòng nằm liền kề nhau.

Do chưa có kinh nghiệm quản lý, các con bò tùy tiện ra vào các phòng không kiểm soát. Trang trại của ông hiện tại có ~n~ con bò, con bò thứ ~i~ đang đứng tại phòng ~x_i~. Do có lệnh cần kiểm tra sức khỏe định kì cho các con bò nên ông muốn tập trung chúng lại. Sẽ có ~k~ bác sĩ thú y đến thực hiện việc kiểm tra này nên ông muốn lùa các con bò về đúng ~k~ phòng.

Để di chuyển sang phòng bên cạnh, mỗi con bò cần 1 đơn vị thời gian. Các con bò sẽ di chuyển tới phòng gần nó nhất trong số ~k~ phòng được chỉ định. Từ nơi đang đứng chúng có thể đi sang một phòng liền kề. Khi đó, thời gian lùa bò được tính là tổng thời gian di chuyển tới phòng kiểm tra được chỉ định của tất cả các con bò.

Để tiết kiệm thời gian, Giáo sư muốn đưa ra một phương án lùa bò sao cho tổng thời gian là nhỏ nhất.

Yêu cầu: Bạn hãy giúp Giáo sư tìm tổng thời gian ít nhất để lùa các con bò về đúng ~k~ phòng.

Input

Vào từ tệp văn bản TESTROOM.INP gồm:

• Dòng đầu chứa hai số nguyên dương ~n~, ~k~ (~k \leq n \leq 10^4~) lần lượt là số con bò và số phòng để lùa bò về đó.

• Dòng tiếp chứa ~n~ số nguyên dương ~x_1, x_2, ..., x_n~ (~x_i \leq 10^9~) là chỉ số phòng của ~n~ con bò hiện tại.

Output

Xuất ra tệp văn bản TESTROOM.OUT:

• In ra một số nguyên duy nhất là thời gian để lùa bò theo phương án tối ưu tìm được.

Scoring

Sample Input 1

6 3
9 19 2 11 5 15

Sample Output 1

9

Sau lễ thành hôn của Tấm là các trò chơi dân gian của vương quốc, một trong những trò chơi được ưa chuộng là trò chơi bảng số diễn ra như sau:

Xét bảng số gồm ~3 \times n~, mỗi ô chứa một số nguyên có giá trị tuyệt đối không vượt quá 100.

Ví dụ:

Ta gọi điểm của mỗi cột là tích của ba số trong cột đó, điểm của bảng là tổng tất cả điểm của các cột. Ví dụ bảng trên thì điểm bằng: $$(-3) \times 0 \times 1 + (-1) \times (-3) \times 1 + (-2) \times 2 \times 1 + 0 \times 4 \times 1 + 0 \times 5 \times 1 + 5 \times (-2) \times 1 + (-1) \times 5 \times 1 = -6$$

Ta có loại phép biến đổi bảng như sau: Tráo hai ô liên tiếp trên cùng một dòng cho nhau, điều kiện thực hiện được phép trao là một ô phải khác ~0~ còn ô còn lại phải bằng ~0~.

Yêu cầu: Cho bảng số, hãy biến đổi bảng để được tổng điểm lớn nhất.

Input

Vào từ tệp văn bản GAME.INP gồm:

• Dòng đầu là số ~n~;

• Dòng thứ hai chứa ~n~ số nguyên là các số ghi trên dòng 1 của bảng số;

• Dòng thứ ba chứa ~n~ số nguyên là các số ghi trên dòng 2 của bảng số;

• Dòng thứ tư chứa ~n~ số nguyên là các số ghi trên dòng 3 của bảng số.

Output

Ghi ra tệp văn bản GAME.OUT gồm một dòng chứa một số duy nhất là tổng điểm lớn nhất đạt được.

Sample Input 1

7
-3 -1 -2 0 5 -1 0
0 -3 2 4 0 5 -2
1 1 1 1 1 1 1

Sample Output 1

36

Notes

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài có ~n \leq 5~ và các số ghi trên dòng thứ ba đều bằng ~1~;

• Có 20% test khác ứng với 20% số điểm của bài có ~n \leq 5~;

• Có 20% test khác ứng với 20% số điểm của bài có ~n \leq 10~;

• Có 20% test khác ứng với 20% số điểm của bài có ~n \leq 100~ và các số ghi trên dòng thứ ba đều bằng ~1~;

• Có 20% số test còn lại ứng với 20% số điểm của bài có ~n \leq 100~.