Bài tập

Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước số là 1 và chính nó.

Cho một dãy số nguyên gồm \(n\) phần tử \(a_1, a_2, \dots, a_n\).

Yêu cầu: Hãy tìm đoạn con có các phần tử liên tiếp là số nguyên tố trong dãy số trên sao cho nó có số phần tử là lớn nhất.

Input

Dữ liệu vào: từ tệp văn bản DCNT.INP có cấu trúc:

• Dòng thứ nhất ghi số tự nhiên \(n\) (\(0 < n \le 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^7\)), các số cách nhau một dấu cách.

Output

Dữ liệu ra:
Ghi vào tệp DCNT.OUT duy nhất một số là độ dài đoạn con tìm được theo yêu cầu.

Example

6
1 5 3 2 7 4

4

Scoring

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài có \(n \le 10^3\), \(|a_i| \le 10^3\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài có \(n \le 10^4\), \(|a_i| \le 10^6\).
• Có \(40\%\) số test khác ứng với \(40\%\) số điểm với trường hợp còn lại.

Một dãy số gồm \(M\) phần tử \(a_1, a_2, \dots, a_M\) được gọi là dãy số hai phía nếu thoả mãn đồng thời các điều kiện sau:

• \(M\) chẵn, khi đó chia dãy thành hai phần \(\{a_1, a_2, \dots, a_{M/2}\}\) và \(\{a_{M/2+1}, \dots, a_M\}\);
• Các phần tử ở mỗi phần có giá trị bằng nhau, tức là \(a_1 = a_2 = \dots = a_{M/2}\) và \(a_{M/2+1} = \dots = a_M\);
• Giá trị của hai phần phải khác nhau, tức là \(a_1 \ne a_M\).

Ví dụ:

• Là dãy số hai phía: \(\{0,0,0,1,1,1\}\), \(\{1,1,2,2\}\), …
• Không phải dãy hai phía: \(\{1,1,0\}\), \(\{0,0,2,1\}\), \(\{2,2\}\), …

Cho dãy số gồm \(N\) phần tử, mỗi phần tử nhận một trong ba giá trị \(0, 1, 2\) và số nguyên dương \(K\).

Yêu cầu. Hãy thay đổi không quá \(K\) phần tử của dãy số (mỗi phần tử được đổi thành một trong ba giá trị \(0, 1, 2\)) sao cho tồn tại một dãy con liên tiếp là dãy số hai phía có độ dài lớn nhất. In ra độ dài lớn nhất đó.

\InputFile

• Dòng đầu tiên chứa hai số nguyên \(N, K\) \((1 \le K \le N \le 10^5)\).
• Dòng thứ hai chứa \(N\) số, mỗi số nhận một trong ba giá trị \(0\), \(1\) hoặc \(2\) mô tả dãy số ban đầu.

\OutputFile

• Một số nguyên duy nhất là độ dài lớn nhất của dãy số hai phía tìm được sau khi thay đổi không quá \(K\) số của dãy đã cho.

\Examples
\beginexample
\exmp
7 3
2 1 2 0 0 2 1

6

\exmp
4 2
1 1 0 0

4

\endexample

\Note
Ở ví dụ thứ nhất, có thể đổi dãy thành \(2\;2\;2\;0\;0\;0\;1\) (hoặc \(1\;1\;1\;0\;0\;0\;1\)); khi đó \(6\) phần tử đầu tạo thành một dãy số hai phía có độ dài \(6\).

Ở ví dụ thứ hai, dãy đã là dãy hai phía nên không cần thay đổi phần tử nào.

\Scoring

• (\(50\%\)) \(1 \le K \le N \le 10^2\);
• (\(30\%\)) \(1 \le K \le N \le 10^3\);
• (\(20\%\)) Không có ràng buộc thêm.

\endproblem

Nhập vào 4 số nguyên a, b, c, d. Nếu a và b là giá trị lớn nhất trong các số, thì in ra a + b. Ngược lại nếu c và d là giá trị lớn nhất trong các số, thì in ra c + d. Ngược lại in ra a + b + c + d.

Example

6 14 5 13

38

10 5 8 4

27

8 8 8 2

16

1 12 2 13

28

Viết chương trình nhập vào hai dãy số nguyên dương \(a\) và \(b\). Dãy \(a\) có \(N\) phần tử, dãy \(b\) có \(M\) phần tử. Đếm số lượng giá trị trong đoạn \([1, 1000]\), xuất hiện ở cả hai dãy \(a\) và \(b\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) - số lượng phần tử dãy \(a\) và dãy \(b\). \((1 \leq N, M \leq 1000)\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) - giá trị các phần tử của dãy \(a\) \((1 \leq a_i \leq 1000)\).
• Dòng thứ ba gồm \(M\) số nguyên dương \(b_1, b_2, ..., b_M\) - giá trị các phần tử của dãy \(b\) \((1 \leq b_i \leq 1000)\).

Output

Một dòng duy nhất là số lượng giá trị nằm trong đoạn \([1, 1000]\) xuất hiện ở cả hai dãy \(a\) và \(b\).

Example

5 6
2 2 3 3 4
2 3 4 6 8 2

3