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 \le L < R \le 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 \(N\) số nguyên \(A_1,A_2,...,A_N\) (\(|A_i| \le 10^9, 1 \le i \le N\)).

Output

• 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.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^4\).
• Subtask \(3\) (\(30\%\) số điểm): \(N \le 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 thì 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 \neq 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

• Một dòng chứa hai số nguyên dương \(n,m\) (\(m \le 10^9\)).

Output

• 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,...,v_n\) là ước giá của \(n\) vật, hãy được ra tổng ước giá các vật đem bán nhỏ nhất.

Input

• Gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu 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

• 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