Số nguyên tố là số nguyên dương lớn hơn \(1\) và chỉ có hai ước. Các số nguyên tố đầu tiên \(2,3,5,7,11,…\) Hợp số là các số nguyên dương lớn hơn \(1\) và không là số nguyên tố. Các hợp số đầu tiên \(4,6,8,9,10,12,…\)
Cho hai số nguyên dương \(N,K\) và dãy số nguyên dương \(a_1,a_2,…,a_N\). Một dãy con liên tiếp của dãy đã cho gồm các phần tử \(a_i,a_{i+1},a_{i+2},…,a_j (1≤i<j≤N)\) được gọi là dãy số đẹp nếu dãy con đó có số lượng số nguyên tố gấp \(K\) lần số lượng hợp số.
Yêu cầu:
- Hãy tìm các dãy số đẹp dài nhất của dãy \(a_1,a_2,…,a_N\).
Dữ liệu vào:
- Dòng 1: Ghi số nguyên dương \(N\) và \(K (K≤N≤10^5\));
- Dòng 2: Ghi \(N\) số nguyên dương \(a_1,a_2,…,a_N (2≤a_i≤10^6,1≤i≤ N)\).
Kết quả:
- Dòng 1: Ghi ra số lượng phần tử của dãy số đẹp dài nhất tìm được;
- Dòng 2: Ghi ra vị trí đầu tiên của mỗi dãy số đẹp dài nhất, theo giá trị tăng dần.
Dữ liệu đầu vào đảm bảo có nghiệm. Các số trên một dòng cách nhau bởi một dấu cách.
Ví dụ:
Input
7 2
2 5 6 4 8 5 3
Output
3
1 5
Hình minh họa
Ràng buộc:
- Có 40% test với \(N≤1000;\)
- Có 60% test với ràng buộc gốc.