Perfecte

Se consideră un șir de $n$ numere naturale nenule. Micul Gates caută, pentru fiecare număr în parte, cel mai apropiat pătrat perfect de el, înlocuind numărul cu baza pătratului perfect găsit (cea negativă dacă pătratul perfect este mai strict mic decât numărul, cea pozitivă dacă pătratul perfect este mai mare sau egal cu numărul). De exemplu, pentru numărul $45$ cel mai apropiat pătrat perfect este $49=(-7)^2=7^2$, deci numărul este înlocuit cu $7$, iar dacă numărul este $17$, pătratul perfect cel mai apropiat este $16=(-4)^2=4^2$ deci numărul este înlocuit cu $-4$.
Se formează în acest fel un nou șir pentru care Micul Gates dorește să afle:

Cerință

1. Care este numărul cel mai mare pe care îl găsește de cele mai multe ori în noul șir.
2. Care este cea mai scurtă secvență în care numerele sunt distincte cu excepția unuia singur, care apare de două ori, afisând lungimea secvenței găsite, poziția de unde începe și poziția unde se termină aceasta. Dacă există mai multe secvențe de acest fel, o alege cea mai din stânga. O secvență poate fi alcătuită și din două elemente.

Date de intrare

Fișierul de intrare perfecte.in conține de prima linie numărul $c$ al cerinței, care poate fi doar $1$ sau $2$. Pe a doua linie se găsește un număr natural $n$ nenul, iar pe a treia linie sunt $n$ numere naturale nenule separate printr-un spațiu, cu semnificația din enunț.

Date de ieșire

Fișierul perfecte.out va conține, pe prima linie, dacă cerința este $1$ o valoare corespunzătoare cerinței $1$, sau $3$ valori separate prin câte un spațiu dacă cerința este $2$.

Restricții și precizări

• $1 \leq n \leq 1 \ 000 \ 000$;
• Numerele din șir au valorile maxim $1 \ 000 \ 000$;
• Se garantează că pentru fiecare test există soluție;
• Pentru cerinta $1$, se acordă $32$ de puncte;
• Pentru cerinta $2$, se acordă $68$ de puncte.

Exemplul 1

perfecte.in

1
4
45 20 25 23

perfecte.out

5

Explicație

Cerinta este $1$, $n=4$, pentru fiecare număr din șir se găsește baza conform cerinței și șirul devine: $7$, $-4$, $5$, $5$, deci numărul care apare de cele mai multe ori în noul șir este $5$.

Exemplul 2

perfecte.in

2
6
25 20 45 23 19 31

perfecte.out

4 1 4

Explicație

Cerinta este $2$, $n=6$, pentru fiecare număr din șir se găsește baza conform cerinței și șirul devine: $5$, $-4$, $7$, $5$, $-4$, $6$ deci secvența cerută este formată din $5$, $-4$, $7$, $5$, are lungimea $4$ și are pozițiile de început și sfârșit $1$ și $4$.