Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_01_06 - Ruchy tektoniczne

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..106].

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

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

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 [-107.. 107]).

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

Dodane przez:Marcin Kasprowicz
Data dodania:2014-03-26
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:FRAKTAL
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.