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

Se consideră un șir de N numere naturale X[i], 1 ≤ i ≤ N, unde N este un număr natural. O secvență este un subșir format din numere aflate pe poziții consecutive în șirul dat. 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ța

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 primul rând 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 = 1, în fișierul de ieșire oneout.out se va scrie numărul de numere libere de pătrate din șir. Dacă C = 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 ≤ N ≤ 1.000.000
• 2 ≤ X[i] ≤ 1.000.000, 1 ≤ i ≤ N
• Lungimea unei bisecvențe reprezintă numărul de numere din aceasta.
• Datorită dimensiunilor prea mari ale testelor, s-au adăugat doar o parte din ele

Exemplul 1:

oneout.in

1
6
10 2 12 7 8 15

oneout.out

4

Explicație

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

Exemplul 2:

oneout.in

2
6
10 2 12 7 8 15

oneout.out

3 1
1 4

Explicație

C = 2, N = 6, X1-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ă egală cu 3, care începe în poziția 1 și se termină în poziția 4.

Exemplul 3:

oneout.in

2
7
5 28 17 24 15 20 18

oneout.out

2 2
1 3
3 5

Explicație

C = 2, N = 7, X1-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ă egală cu 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.

Exemplul 4:

oneout.in

2
9
3 10 5 8 9 11 4 15 21

oneout.out

3 1
6 9

Explicație

C = 2, N = 9, X1-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.