oneout

Definim un număr liber de pătrate ca fiind un număr natural care nu are ca divizor niciun pătrat perfect mai mare ca $1$. Prin convenție, $1$ este considerat liber de pătrate.

Așadar, șirul numerelor libere de pătrate este: $1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, \dots$

Se consideră un șir de $N$ numere naturale $X_i$, $1 \leq i \leq N$, unde $N$ este un număr natural.

Definim o bisecvență ca un subșir nevid obținut prin eliminarea dintr-o secvență a unui număr care nu este la începutul sau la sfârșitul secvenței.

Cerințe

1. Să se determine câte numere libere de pătrate conține șirul dat.
2. Să se determine cea mai lungă bisecvență din șir formată din numere libere de pătrate, obținută prin eliminarea unui număr care nu este liber de pătrate.

Date de intrare

Fișierul de intrare oneout.in conține pe prima linie un număr natural $C$, care poate fi doar $1$ sau $2$, reprezentând cerința, pe a doua linie numărul natural $N$ iar pe a treia linie $N$ numere naturale, separate prin câte un spațiu, cu semnificația de mai sus.

Date de ieșire

Dacă $C$ este egal cu $1$, în fișierul de ieșire oneout.out se va scrie numărul de numere libere de pătrate din șir.

Dacă $C$ este egal cu $2$:

• Pe prima linie a fișierului de ieșire oneout.out se vor scrie două numere $L$ și $K$ despărțite printr-un spațiu, unde $L$ reprezintă lungimea maximă a unei bisecvențe cu proprietățile cerute, iar $K$ reprezintă numărul de bisecvențe de lungime maximă existente în șir.
• Pe următoarele $K$ linii se vor scrie indicii de început și de sfârșit ai fiecărei bisecvențe de lungime maximă găsite, în ordinea crescătoare a indicelui de start, despărțite printr-un spațiu.
• Dacă șirul nu conține nicio bisecvență cu proprietățile cerute, în fișierul de ieșire se va scrie -1.

Restricții și precizări

• $3 \leq N \leq 10^6$
• $2 \leq X_i \leq 10^6$, $1 \leq i \leq N$
• Lungimea unei bisecvențe reprezintă numărul de numere din aceasta.
• Pentru teste în valoare de 37 de puncte $C = 1$, din care pentru teste în valoare de 24 de puncte $3 \leq N \leq 25$.
• Pentru teste în valoare de 63 de puncte $C = 2$, din care pentru teste în valoare de 23 de puncte $3 \leq N \leq 101$.

Exemplu 1

oneout.in

1
6
10 2 12 7 8 15

oneout.out

4

$C = 1$, $N = 6$, $X_{1–6} = \{10, 2, 12, 7, 8, 15\}$. Se rezolvă prima cerință.
Sunt $4$ numere libere de pătrate în șirul $X_{1–6}$ și anume $10$, $2$, $7$ și $15$.

Exemplu 2

oneout.in

2
6
10 2 12 7 8 15

oneout.out

3 1
1 4

$C = 2$, $N = 6$, $X_{1–6} = \{10, 2, 12, 7, 8, 15\}$. Se rezolvă a doua cerință.
Dacă se elimină $12$ se obține bisecvența $\{10, 2, 7\}$ de lungime $3$. Dacă se elimină $8$ se obține bisecvența $\{7, 15\}$ de lungime $2$. Deci există o singură bisecvență de lungime maximă $= 3$, care începe în poziția $1$ și se termină în poziția $4$.

Exemplu 3

oneout.in

2
7
5 28 17 24 15 20 18

oneout.out

2 2
1 3
3 5

$C = 2$, $N = 7$, $X_{1–7} = \{5, 28, 17, 24, 15, 20, 18\}$. Se rezolvă a doua cerință.
Dacă se elimină $28$ se obține bisecvența $\{5, 17\}$ de lungime $2$. Dacă se elimină $24$ se obține bisecvența $\{17, 15\}$ tot de lungime $2$. Deci există două bisecvențe de lungime maximă $= 2$. Prima începe în poziția $1$ și se termină în poziția $3$. A doua începe în poziția $3$ și se termină în poziția $5$.

Exemplu 4

oneout.in

2
9
3 10 5 8 9 11 4 15 21

oneout.out

3 1
6 9

$C = 2$, $N = 9$, $X_{1–9} = \{3, 10, 5, 8, 9, 11, 4, 15, 21\}$. Se rezolvă a doua cerință.
$8$ nu poate fi eliminat deoarece este situat la sfârșitul unei bisecvențe iar $9$ nu poate fi eliminat pentru că ar fi începutul unei bisecvențe.
Singurul număr care nu este liber de pătrate ce poate fi eliminat este $4$ și se va obține bisecvența $\{11, 15, 21\}$ de lungime $3$ care începe în poziția $6$ și se termină în poziția $9$.