canonic

Fermierul Amooot merge la magazinul de furaje pentru a achiziționa amestecuri de iarbă pentru pășunatul vacilor sale. Vânzătorul Popică, viclean de fel, îi prezintă un șir $V$ de $N$ oferte; însă, pentru ca Amooot să poată achiziționa hrana, acesta va trebui neapărat să selecteze o subsecvență canonică de oferte!

Spunem că o subsecvență $a_i, a_{i+1}, \ldots, a_j$, $1 \leq i \leq j \leq N$ este canonică dacă $a_k \text{ \% } a_i = 0$, pentru orice $k$, $i \leq k \leq j$.
De exemplu, în șirul $(3, 4, 2, 10, 4, 12, 3)$, subsecvențe canonice sunt $(2, 10)$ sau $(2, 10, 4, 12)$, dar nu și subsecvența $(10, 4, 12)$.

Cerință

Văzând condițiile impuse de Popică, Amooot își pune două întrebări:

1. Care este cea mai lungă subsecvență canonică din $V$?
2. Câte subsecvențe canonice există în $V$?

Date de intrare

Pe prima linie a fișierului de intrare canonic.in se găsește numărul $C$, numărul cerinței de rezolvat.

Pe a doua linie a fișierului de intrare se găsește numărul $N$, reprezentând numărul elementelor șirului de oferte.

Pe a treia linie a fișierului de intrare se vor găsi $N$ numere naturale, care reprezintă șirul de oferte $V$. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire canonic.out se va afișa răspunsul la cerința din test.

Restricții și precizări

• $C \in \{1, 2\}$
• $1 \leq N \leq 500 \ 000$
• $1 \leq V_i \leq 10^{12}$, pentru orice $1 \leq i \leq N$
• Atenție la limita de memorie!

Exemplul 1

canonic.in

1
7
3 4 2 10 4 12 3

canonic.out

4

Explicație

Subsecvența canonică de lungime maximă din șir este $(2, 10, 4, 12)$. Așadar, lungimea maximă este $4$.

Exemplul 2

canonic.in

2
7
3 4 2 10 4 12 3

canonic.out

11

Explicație

Subsecvențele canonice din șir sunt:

1. $(3)$
2. $(4)$
3. $(2)$
4. $(2, 10)$
5. $(2, 10, 4)$
6. $(2, 10, 4, 12)$
7. $(10)$
8. $(4)$
9. $(4, 12)$
10. $(12)$
11. $(3)$