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