Bài tập

Cho dãy \(A\) gồm \(N\) số nguyên dương. Với mỗi truy vấn \((u, v)\), xét đoạn \(A_u, A_{u+1}, \dots, A_v\). Ta cắt đoạn này tại một vị trí nào đó thành hai phần: phần đầu (tiền tố) và phần sau (hậu tố); một trong hai phần được phép rỗng. Hãy tìm giá trị nhỏ nhất của \(|S_1 - S_2|\), với \(S_1\), \(S_2\) lần lượt là tổng của hai phần.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, \dots, A_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một truy vấn.

Output

In ra \(Q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Constraints

• \(1 \le N, Q \le 10^5\).
• \(1 \le A_i \le 10^9\).
• \(1 \le u \le v \le N\).

Sample Input

6 2
2 7 1 8 2 8
1 4
3 6

Sample Output

0
1

Explanation

Truy vấn \((1,4)\): đoạn \(2,7,1,8\) chia thành \((2,7)\) và \((1,8)\), cùng tổng \(9\), chênh lệch \(0\). Truy vấn \((3,6)\): đoạn \(1,8,2,8\) chia thành \((1,8)\) và \((2,8)\) có tổng \(9\) và \(10\), chênh lệch \(1\).

Cho hai xâu \(A\) và \(B\) gồm các chữ cái thường. Gọi \(L\) là độ dài xâu con chung dài nhất của \(A\) và \(B\).

Ta muốn chèn đúng một chữ cái thường vào một vị trí nào đó của \(A\) (đầu xâu, cuối xâu hoặc giữa hai ký tự liên tiếp; xâu \(A\) có \(|A| + 1\) vị trí chèn) sao cho độ dài xâu con chung dài nhất của xâu mới và \(B\) trở thành \(L + 1\).

Hãy đếm số cặp (vị trí chèn, chữ cái được chèn) thoả mãn. Hai cặp có vị trí khác nhau luôn được tính là hai cách khác nhau, kể cả khi xâu thu được giống nhau.

Input

• Dòng thứ nhất chứa xâu \(A\).
• Dòng thứ hai chứa xâu \(B\).

Output

In ra một số nguyên là số cách chèn thoả mãn.

Constraints

• \(1 \le |A|, |B| \le 1010\)
• Hai xâu chỉ gồm chữ cái tiếng Anh viết thường.

Sample Input

abc
cbad

Sample Output

9

Explanation

Xâu con chung dài nhất của abc và cbad có độ dài \(1\). Có \(9\) cách chèn để độ dài này tăng lên \(2\), chẳng hạn chèn d vào cuối abc được abcd (có xâu con chung ad), hoặc chèn b vào đầu abc được babc (có xâu con chung ba).

Một xưởng cưa tính tiền cắt gỗ theo chiều dài của thanh đang được cắt: mỗi nhát cắt tốn số tiền bằng chiều dài của đoạn gỗ chứa nhát cắt đó, và mỗi lần chỉ cắt được một nhát.

Cho một thanh gỗ dài \(L\) mét và \(n\) vị trí cần cắt (tính từ một đầu thanh). Thứ tự thực hiện các nhát cắt ảnh hưởng đến tổng chi phí. Ví dụ, thanh dài \(10\) cần cắt ở \(2, 4, 7\): cắt lần lượt \(2 \to 4 \to 7\) tốn \(10 + 8 + 6 = 24\), còn cắt \(4 \to 2 \to 7\) tốn \(10 + 4 + 6 = 20\).

Hãy tính tổng chi phí nhỏ nhất để cắt thanh gỗ tại đủ \(n\) vị trí đã cho.

Input

Dữ liệu gồm nhiều bộ test. Mỗi bộ test gồm:

• dòng thứ nhất: số nguyên \(L\) (chiều dài thanh);
• dòng thứ hai: số nguyên \(n\) (số vị trí cắt);
• dòng thứ ba: \(n\) số nguyên \(c_1 < c_2 < \dots < c_n\), các vị trí cần cắt.

Dữ liệu kết thúc bằng một dòng chứa \(L = 0\) (không phải bộ test).

Output

Với mỗi bộ test in ra trên một dòng chi phí nhỏ nhất.

Constraints

• \(2 \le L \le 999\)
• \(1 \le n \le 49\), \(0 < c_i < L\), dãy \(c\) tăng ngặt
• Có không quá \(100\) bộ test.

Sample Input

20
3
5 8 14
9
4
2 3 5 7
0

Sample Output

40
21

Explanation

Với bộ đầu tiên: cắt tại \(8\) trước (tốn \(20\)), đoạn \([0,8]\) cắt tại \(5\) (tốn \(8\)), đoạn \([8,20]\) cắt tại \(14\) (tốn \(12\)); tổng \(40\).

Một cấp số cộng là dãy số mà hiệu của hai phần tử liên tiếp luôn bằng một hằng số \(D\) gọi là công sai. Ví dụ \(3, 5, 7, 9\) là cấp số cộng với công sai \(2\).

Cho dãy \(A\) gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\). Ta chọn một số phần tử của \(A\), giữ nguyên thứ tự xuất hiện (dãy con, các vị trí không cần liền kề) sao cho dãy con nhận được \(B_1, B_2, \dots, B_k\) thoả mãn \(B_i = B_{i-1} + D\) với mọi \(i \ge 2\). Công sai \(D\) do bạn tự chọn trong khoảng \(1 \le D \le 50\).

Hãy tìm độ dài lớn nhất \(k\) của một dãy con như vậy (dãy con chỉ có một phần tử luôn thoả mãn).

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

In ra một số nguyên là độ dài lớn nhất của dãy con là cấp số cộng với công sai \(D \in [1, 50]\).

Constraints

• \(1 \le N \le 2000\)
• \(1 \le a_i \le 10^9\)

Sample Input

9
4 21 6 15 8 33 10 12 3

Sample Output

5

Explanation

Chọn \(D = 2\) và dãy con \(4, 6, 8, 10, 12\) (các phần tử còn lại bị bỏ qua), độ dài \(5\). Không có cách nào dài hơn.