POLSKI SPOJ

Profesor Algobit w wolnych chwilach (np. na wakacjach) zajmuje się geologią. Tym razem bada tereny podatne na ruchy tektoniczne. Interesuje go, jak często zmienia się różnica między najwyższym a najniższym punktem na pewnym obszarze. Dla uproszczenia, nie bada całego obszaru, tylko obszar w zdłuż pewnej prostej, na której oznaczył sobie czujniki oddalone od siebie o pewną jednostkę. Profesor czasami potrzebuje tylko wyniku dla pewnego ograniczonego przedziału. Niestety na wakacjach zepsuł mu się komputer i poprosił Ciebie o napisanie programu, który zautomatyzuje obliczenia profesora.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę czujników (numerację zacznamy od 1), gdzie n należy do przedziału [1..10⁶].

W drugim wierszu n liczb całkowitych należących do przedziału [-10⁷.. 10⁷], określających wysokość danego czujnika nad poziomem morza.

Następnie jedna liczba q będąca liczbą zaptyań (q ≤ 10⁷).

Każde zapytanie składa się z liczby o, która należy do zbioru: {0, 1}. Jeśli o ma wartość 0, to podane są jeszcze dwie liczby a i b, gdzie 1≤ a ≤ b ≤ n, to zapytanie o różnicę poziomów między początkiem w a i końcem w b, natomiast, jeśli o ma wartość 1, to podane są trzy liczby a, b oraz v, oznaczające, że w przedziale [a..b], czujniki zanotowały zmianę o v jednostek nad poziomem morza (1≤ a ≤ b ≤ n oraz v należy do przedziału [-10⁷.. 10⁷]).

Wyjście

Dla każdego o mającego wartość 0 należy wypisać maksymalną różnicę poziomów w przedziale [a..b].

Przykład

Wejście:
5
1 3 2 1 8 
5
1 1 3 2
0 1 5 
0 1 3 
1 4 5 -3
0 1 5 

Wyjście:
7
2
7