eolymp
bolt
Try our new interface for solving problems
Problems

Винни-Пух 2

Винни-Пух 2

Time limit 2 seconds
Memory limit 128 MiB

Если вы читали предыдущую задачу, то знаете историю про Винни-Пуха, в этой задаче происходит все то же самое, но теперь иногда Винни меняет сразу множество бочонков на другие. Но он по-прежнему может менять только рядом стоящие бочонки, для того, чтобы было удобно вести учет. Кроме того, мы знаем, что если он меняет бочонки, то все новые будут из одной партии, следовательно, и сладость их будет одинаковой. Ваша задача снова найти максимально возможное количество бочонков, которыми может позавтракать медвежонок.

Input data

В первой строке находится одно число N (1N10^6) – количество бочонков в погребе Винни-Пуха. В следующей строке находится N чисел – сладости бочонков (все числа не превышают 10^9). Далее следует число M (1M10^5) количество запросов. Затем идет М строк, первое число в строке – это вид запроса. Если оно равно 1, то далее будут два числа, l и r (1lrN) и Вам надо посчитать ответ на задачу. Если же номер запроса 2, то далее следует три числа l, r, v, и это означает, что в бочонках с номерами от l до r изменилась сладость и теперь она равна v.

Output data

Для каждого запроса с номером один выведите максимальное количество бочонков на промежутке [l; r], которые идут подряд и сладость всех, кроме первого не меньшая сладости предыдущего.

Examples

Input example #1
10
1 2 3 4 5 5 4 3 2 1
4
1 1 10
2 3 7 3
1 1 10
1 3 5
Output example #1
6
8
3
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013