Злісний вчитель в МШП любить мучити дітей складними завданнями. А якщо діти ці завдання не вирішують, вчитель піддає їх найжорстокішим покаранням. Цього разу він вигадав таке завдання:

Рейтинг усіх учнів МШП записаний у масив \(A\)

Запити вчителя такі:

• Змінити рейтинг \(i\)-го учня на число \(x\)
• Знайти максимальну послідовність нулів (безперспективних учнів), що йдуть поспіль, у масиві \(A\) на відрізку [\(l, r\)].

Допоможіть бідним учням МШП уникнути звірячого покарання за невирішення завдання цього разу.

Формат вхідних даних

У першому рядку вхідного потоку записано число \(N\) \((1 ≤ N ≤ 500000)\) – кількість учнів у МШП.

У другому рядку записано \(N\) чисел – їх рейтинги, числа за модулем не перевищують 1000 (за кількістю завдань, які учень вирішив чи не вирішив під час навчання).

У третьому рядку записано число \(M\) \((1 ≤ M ≤ 50000)\) – кількість запитів.

Кожен із наступних \(M\) рядків містить опис запитів:

UPDATE i x – оновити \(i\)-ий елемент масиву значенням \(x\) \((1 ≤ i ≤ N, |x| ≤ 1000)\)

QUERY l r – знайти довжину максимальної послідовності з нулів на відрізку від \(l\) до \(r\). (\(1 ≤ l ≤ r ≤ N\))

Формат вихідних даних

У вихідний аотік виведіть відповіді на запити QUERY у тому самому порядку, що й у вхідних даних

Приклад вхідних даних

5
328 0 0 0 0
5
QUERY 1 3
UPDATE 2 832
QUERY 3 3
QUERY 2 3
UPDATE 2 0

Приклад вихідних даних

2
1
1