Solução por Leonardo Paes
Conhecimento prévio necessário:
Para resolvermos esse problema, uma observação importante para que um intervalo $$[l, r]$$ seja válido é: $$min(l, r) = mdc(l, r)$$, onde $$min(l, r)$$ é o mínimo $$a_i$$ no intervalo $$[l, r]$$ e $$mdc(l, r)$$ é o máximo divisor comum do intervalo $$[l, r]$$ do vetor $$a$$.
Uma maneira de provar isso é: Suponha que existe um inteiro $$x$$ que divide um outro inteiro $$y$$, tal que $$x > y$$. Isso por si só gera um absurdo, pois o maior divisor de $$y$$ é $$y$$.
Então, está provado por absurdo que $$min(l, r) = mdc(l, r)$$ deve ser verdade para que o intervalo $$[l, r]$$ seja um candidato à resposta.
Então, suponha que nós fixemos $$a_i$$ como parte de um intervalo $$[l, r], l \leq i \leq r$$ tal que $$min(l, r) = mdc(l, r) = a_i$$. Para cada inteiro $$i, 1 \leq i \leq n$$, nós iremos fixá-lo. Para saber o maior intervalo que contém $$a_i$$, podemos fazer duas buscas binárias, uma tentando diminuir ao máximo o $$l$$ do intervalo, e outra tentando aumentar ao máximo o $$r$$ do intervalo. Para checarmos se as respectivas bordas mantém a condição $$min(l, r) = mdc(l, r) = a_i$$ verdadeira, iremos utilizar uma estrutura de dados que nos responde, para qualquer intervalo $$[l, r]$$ do vetor $$a$$, o seu mínimo e o seu máximo divisor comum, em $$O(1)$$.
Essa estrutura de dados é chamada de Sparse Table. Iremos utilizar duas Sparse Tables, uma de mínimo e outra de máximo. Note que ambas as operações são comutativas, ou seja, a ordem das operações não altera o resultado. Portanto, elas satisfazem o pré-requisito para que a Sparse Table funcione!
Código de Exemplo: