Tin học trẻ B - Vòng Khu vực 2021

Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,A_N\) đây là thông tin về một kho báu. Một đoạn con \((L,R)\) của dãy là một dãy gồm các phần tử liên tiếp \(A_L,A_{L+1},...,A_R\) với \(1\leq L<R\leq N\), đoạn con \((L,R)\) được gọi là chứa thông tin quan trọng nhất nếu:

• Phần tử đầu tiên bằng phần tử cuối cùng (\(A_L=A_R\)).
• Tổng các phần tử của đoạn là lớn nhất có thể.

Yêu cầu: Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Input

• Dòng thứ nhất chứa số nguyên dương \(N\).
• Dòng thứ hai chứa số nguyên \(A_1,A_2,...,A_N\text{ }(|A_i|\leq 10^9,1\leq i\leq N)\).

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của đoạn con chứa thông tin quan trọng nhất.

Constraints

• \(N\leq 10^5\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^2\)
• Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^3\)
• Subtask \(3\) (\(30\%\) số điểm): \(N\leq 10^5\)

Example

7
3 3 3 3 1 11 1

13

Alice và Bob đã tìm thấy kho báu, nhưng để mở được kho báu cả hai phải giải câu đố sau:
Cho một số nguyên dương \(n\), một tập con của tập {\(1, 2, ... n\)} gọi là tập \(fset\) nếu không tồn tại hai
số \(u, v (u \ne v)\) thuộc tập mà \(u \times v\) là số chính phương. Số chính phương là bình phương của một
số nguyên. Hãy đếm số cách chọn tập \(fset\) ? Hai cách chọn tập được gọi là khác nhau nếu tồn tại
một số xuất hiện trong cách chọn tập này nhưng không xuất hiện trong cách chọn tập kia.

Yêu cầu: Cho \(n, m\) gọi \(s\) là số cách chọn tập \(fset\), hãy tính \(s\) % \(m\), trong đó là phép toán chia %
lấy dư.

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương \(n, m (m \le 10^9)\)

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số là giá trị \(s\) % \(m\).

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(n \le 10\)
• Subtask \(2\) (\(24\%\) số điểm): \(n \le 50\)
• Subtask \(3\) (\(16\%\) số điểm): \(n \le 1000\)
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^5\)
• Subtask \(5\) (\(24\%\) số điểm): \(n \le 10^6\)

Example

4 100

12

Sau khi giải xong câu đố, Alice và Bob đã mở được kho báu. Kho báu gồm \(n\) vật, cả hai quyết định phân chia các vật lấy được theo nguyên tắc sau:

• Bước 1: Cả hai cùng nhau ước giá \(n\) vật, vật thứ \(i\) (\(1 \le i \le n\)) được ước giá là \(v_i\).
• Bước 2: Chọn một số vật, phân chia các vật đã chọn thành hai phần mà tổng ước giá của hai phần là bằng nhau, mỗi người nhận một phần.
• Bước 3: Các vật còn lại sẽ đem bán rồi chia đều cho cả hai. Để hạn chế phải bán các vật, Alice và Bob thống nhất tổng ước giá các vật đem bán là nhỏ nhất.

Yêu cầu: Cho \(v_1, v_2, \dots, v_n\) là ước giá của \(n\) vật, hãy đưa ra tổng ước giá các vật đem bán nhỏ nhất.

Input

Dữ liệu vào từ thiết bị vào chuẩn gồm nhiều bộ dữ liệu, mỗi bộ có khuôn dạng sau:

• Dòng đầu chứa số nguyên \(n\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(v_i\).

Output

• Ghi ra thiết bị ra chuẩn gồm nhiều dòng, mỗi dòng chứa một số nguyên là tổng ước giá các vật đem bán nhỏ nhất tìm được tương ứng với dữ liệu vào.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 12; v_i \le 10^9\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 24; v_i \le 10^9\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 48; v_i \le 10^2\).
• Subtask \(4\) (\(30\%\) số điểm): \(n \le 96; v_i \le 10^3\).

Example

3
1
2
3
4
2
2
4
1

0
1