Bài tập

Bạn được trao một mảng số nguyên \(d_1, d_2, \dots, d_n\) gồm \(n\) số nguyên. Hãy tưởng tượng bạn đang tham gia một trò chơi số học, nơi bạn cần tìm cách chia mảng này thành ba phần (một số phần có thể rỗng) sao cho mỗi phần tử của mảng thuộc về đúng một trong ba phần và mỗi phần tạo thành một đoạn liên tiếp (có thể rỗng) của mảng ban đầu.

Gọi tổng các phần tử của phần thứ nhất là $sum_1$, tổng các phần tử của phần thứ hai là $sum_2$ và tổng các phần tử của phần thứ ba là $sum_3$. Trong tất cả các cách chia mảng, bạn cần chọn một cách sao cho $sum_1 = sum_3$ và giá trị $sum_1$ lớn nhất có thể.

Cụ thể hơn, nếu phần thứ nhất của mảng chứa $a$ phần tử, phần thứ hai chứa $b$ phần tử và phần thứ ba chứa $c$ phần tử, ta có:

• \(sum_1 = \sum_{1 \leq i \leq a} d_i\)
• \(sum_2 = \sum_{a+1 \leq i \leq a+b} d_i\)

• \(sum_3 = \sum_{a+b+1 \leq i \leq a+b+c} d_i\)

  Tổng của một mảng rỗng được xem là 0.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) --- số phần tử của mảng \(d\).
• Dòng thứ hai chứa \(n\) số nguyên \(d_1, d_2, \dots, d_n\) (\(1 \leq d_i \leq 10^9\)) --- các phần tử của mảng.

Output

• In ra một số nguyên duy nhất --- giá trị lớn nhất có thể của \(sum_1\), thỏa mãn điều kiện \(sum_1 = sum_3\).

  Rõ ràng, luôn tồn tại ít nhất một cách chia hợp lệ (sử dụng \(a = c = 0\) và \(b = n\)).

Example

5
1 3 1 1 4

5

5
1 3 2 1 4

4

3
4 1 2

0

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 100\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 1000\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho một dãy \(A\) gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Yêu cầu: Hãy tìm đoạn con \([l, r]\) \((1 \le l \le r \le N)\) gồm các phần tử liên tiếp \(a_l, a_{l+1}, \dots, a_{r-1}, a_r\) của dãy \(A\) sao cho tổng \(a_l + a_{l+1} + \dots + a_{r-1} + a_r\) là lớn nhất.

Input

Đọc từ file MAXS.INP gồm:

• Dòng đầu tiên chứa số nguyên dương \(N\) \((N \le 10^5)\) là số phần tử trong dãy;
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((|a_i| \le 10^9, 1 \le i \le N)\).

Output

Ghi ra file MAXS.OUT một số nguyên là tổng lớn nhất tìm được.

Example

6
2 -3 8 4 -5 3

12

Scoring

• 20% số test: \(N \le 100\)
• 20% số test: \(N \le 10^4\)
• 20% số test: \(N \le 10^5\) và \(a_i \ge 0\) \((1 \le i \le N)\)
• 40% số test: \(N \le 10^5\)

Nông dân John quyết định mang nước tới cho \(N\) đồng cỏ của mình, để thuận tiện ta đánh số các đồng cỏ từ \(1\) đến \(N\). Để tưới nước cho \(1\) đồng cỏ John có thể chọn \(2\) cách, \(1\) là đào ở đồng cỏ đó \(1\) cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ trước đó đã có nước tới.

Để đào một cái giếng ở đồng cỏ \(i\) cần \(1\) số tiền là \(W_{i}\). Lắp ống dẫn nước nối \(2\) đồng cỏ \(i\) và \(j\) cần một số tiền là \(P_{ij}\).

Tính xem nông dân John phải chi ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(N\) \((1 \leq N \leq 300)\) - số lượng đồng cỏ.

• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa 1 số nguyên duy nhất \(W_i\) \((1 \leq W_i \leq 100,000)\).

• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên cách nhau bởi dấu cách, số thứ \(j\) là \(P_{ij}\) \((1 \leq P_{ij} \leq 10^{5}, P_{ij} = P_{ji}, P_{ii} = 0)\).

Output

• Một số nguyên duy nhất là chi phí tối thiểu để cung cấp nước cho tất cả các đồng cỏ.

Example

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

9

    Nông dân John có thể đào $1$ cái giếng ở đồng cỏ thứ $4$ và lắp ống dẫn nối đồng cỏ $1$ với tất cả $3$ đồng cỏ còn lại, chi phí tổng cộng là $3 + 2 + 2 + 2 = 9$.

Cho một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^5, 1 \leq i \leq n \leq 10^5\)).

**Yêu cầu:** Tìm số $a_i$ có số ước nguyên dương nhiều nhất, nếu có nhiều số như vậy thì in ra số xuất hiện đầu tiên trong các số đó.

Input

Dữ liệu: Từ file UOCSO.INP gồm:

• Dòng đầu là số nguyên dương \(n\);
• Dòng tiếp theo là \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Mỗi số cách nhau một khoảng trắng.

Output

Kết quả: Ghi ra file UOCSO.OUT một số nguyên dương duy nhất là kết quả tìm được.

Example

5
10 6 8 7 12

12

4
10 6 8 7

10

Scoring

Ràng buộc:

• Có 80% số điểm ứng với \((1 \leq n \leq 10^5; 1 \leq a_i \leq 10^5)\);
• 20% số điểm còn lại không có ràng buộc gì thêm.