eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Вінні-Пух 2

Вінні-Пух 2

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB

Якщо ви читали попередню задачу, то знаєте історію про Вінні-Пуха, у цій задачі відбувається усе те ж саме, але тепер іноді Вінні міняє відразу множину бочечок на інші. Але він як і раніше може міняти лише бочечки, що стоять поряд, для того, щоб було зручно вести облік. Крім того, ми знаємо, що якщо він міняє бочечки, то усі нові будуть з одніє партії, відповідно, і їх солодості будуть одинакові. Ваша задача знову знайти максимально можливу кількість бочечок, якими може поснідати ведмежа.

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #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
Вихідні дані #1
6
8
3
Автор Олександр Бурков
Джерело Дистанційна Літня Комп`ютерна Школа - літо 2013 року