Par de Números
Flúcio tem um vetor $$a_1, a_2, …, a_n$$, que consiste em $$n$$ números inteiros positivos. Hoje, Flúcio pediu para você encontrar um par de números inteiros $$l, r (1 \leq l \leq r \leq n)$$, de modo que as seguintes condições sejam satisfeitas:
- Existe um número inteiro $$j (l \leq j \leq r)$$, de modo que todos os números inteiros $$a_l, a_{l + 1}, …, a_r$$ são divisíveis por $$a_j$$;
- o valor $$r-l$$ é o valor máximo entre todos os pares para os quais a condição $$1$$ é verdadeira.
Ajude Flúcio a encontrar o par de números $$(l, r)$$ requisitados. Se houver vários pares que satisfaçam as condições acima, encontre todos eles.
Entrada
A primeira linha contém o número inteiro $$n$$. A segunda linha contém $$n$$ números inteiros separados por espaço $$a_1, a_2, …, a_n$$.
Saída
Restrições
- $$1 \leq n \leq 3*10^5$$
- $$1 \leq a_i \leq 10^6$$
Exemplos
| Entrada | Saida |
| 5 4 6 9 3 6 |
1 3 2 |
| 5 1 3 5 7 9 |
1 4 1 |
| 5 2 3 5 7 11 |
5 0 1 2 3 4 5 |