Compras no Shopping

Recentemente Bia deciciu comprar um novo celular. Para isso ela vai aproveitar a viagem que fez para Natal, e vai fazer as compras no maior Shopping da cidade, o Midway Mall.

O Midway Mall é composto de $$n$$ lojas, numeradas entre $$1$$ e $$n$$. Todas elas vendem o celular, embora o preço possa ser diferente em cada loja. Na sua pesquisa decidiu que queria saber em que lojas mais valia a pena comprar, e para issa ela quer sua ajuda.

Você dever responder $$q$$ perguntas da forma $$i\ j$$, onde a resposta será a diferença entre o valor máximo e o valor mínimo do celular entre as lojas $$i$$ e $$j$$. Além disso as lojas podem mudar o preço do celular à vontade, e isso deve ser levado em conta em pesquisas futuras.

Entrada

A primeira linha contém o inteiro $$n,\ (1 \leq n \leq 10^5)$$.

A segunda linha contém $$n$$ inteiros $$p_1, p_2, \dots p_n\ (1 \leq p_i \leq 10^5)$$, indicando o valor do celular na loja $$i$$.

A terceira linha contém um inteiro $$q$$, indicando o número de operações.

As próximas $$q$$ linhas descrevem uma operção cada, da seguinte forma:

• $$1\ i\ p$$, indicando que o preço da loja $$i$$ foi mudado para $$p$$
• $$2\ i\ j$$, indicando uma consulta

Saída

Para cada consulta, imprima uma linha incando a maior diferença de preços das lojas entre as lojas $$i$$ e $$j$$, inclusive.

Exemplos