Intermediário Informática - Semana 41

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