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

Entrada	Saída
4 100 150 90 170 3 2 1 3 1 2 50 2 2 4	60 120