Դուք ստանում եք կախարդական փայտիկների զանգված, որտեղ -րդ փայտիկը ունի a_i երկարություն: Մենք ասում ենք, որ փայտիկների զանգվածը լավ է, եթե գոյություն ունի երեքություն (1 \le i < j < k \le |b|), այնպես որ գոյություն ունի ոչ-դեգեներատիվ եռանկյուն, որի կողմերն են b_i, b_j և b_k:
Դուք խնդրվում եք մշակել հարցումներ երկու տեսակի:
— դիրքում գտնվող կախարդական փայտիկը փոխել է իր երկարությունը -ի;
— տպեք ոչ դատարկ հարակից ենթամասերի առավելագույն քանակը, որոնց մեջ կարող է բաժանվել այնպես, որ յուրաքանչյուր ենթամասը լավ լինի: Խնդրում ենք նկատի ունենալ, որ յուրաքանչյուր տարր պետք է պատկանի լավ ենթամասին: Եթե հատվածը չի կարող բաժանվել ոչ դատարկ հարակից ենթամասերի, պատասխանն է :
Մուտքի առաջին տողում կա երկու ամբողջ թիվ և (1 \le n,q \le 5 \cdot 10^5) — կախարդական փայտիկների զանգվածի երկարությունը և հարցումների քանակը:
Մուտքի երկրորդ տողում կա ամբողջ թիվ a_i (1 \le a_i \le 10^6) — կախարդական փայտիկների երկարությունները զանգվածում:
Հաջորդ տողերից յուրաքանչյուրում կա մեկ հարցում հետևյալ տեսակի:
(1 \le i \le n, 1 \le x \le 10^6);
(1 \le l \le r \le n).
Յուրաքանչյուր տեսակի հարցման համար տպեք մեկ տող մեկ ամբողջ թիվով — առավելագույն ոչ դատարկ հարակից ենթամասերի քանակը, որոնց մեջ հատվածը կարող է բաժանվել այնպես, որ յուրաքանչյուր ենթամասը լավ լինի: Եթե հատվածը չի կարող բաժանվել ոչ դատարկ հարակից ենթամասերի, տպեք :
Example 1
Սկզբնական զանգվածը a = [1, 3, 5, 4, 7, 5, 4, 3, 9, 8]:
Հարցում "2 1 10": Մենք կարող ենք բաժանել ամբողջ զանգվածը լավ ենթամասերի: [1, 3, 5, 4], [7, 5, 4], [3, 9, 8]:
[1, 3, 5, 4] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (3 + 4 > 5):
[7, 5, 4] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (4 + 5 > 7):
[3, 9, 8] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (3 + 8 > 9):
Հարցում "1 3 3": Զանգվածը դառնում է a = [1, 3, 3, 4, 7, 5, 4, 3, 9, 8]:
Հարցում "2 1 10": Մենք կարող ենք բաժանել ամբողջ զանգվածը լավ ենթամասերի: [1, 3, 3], [4, 7, 5], [4, 3, 9, 8]:
[1, 3, 3] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (1 + 3 > 3):
[4, 7, 5] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (4 + 5 > 7):
[4, 3, 9, 8] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (4 + 8 > 9):
Հարցում "2 1 7": Ունեցած ենթամասը [1, 3, 3, 4, 7, 5, 4]: Մենք կարող ենք բաժանել այն լավ ենթամասերի: [1, 3, 3] և [4, 7, 5, 4]:
[1, 3, 3] լավ է: 1 + 3 > 3:
[4, 7, 5, 4] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (4 + 4 > 5):
Հարցում "2 3 8": Ունեցած ենթամասը [3, 4, 7, 5, 4, 3]: Մենք կարող ենք բաժանել այն լավ ենթամասի: [3, 4, 7, 5, 4, 3]:
[3, 4, 7, 5, 4, 3] լավ է: , , երկարությամբ փայտիկները կազմում են եռանկյուն (3 + 4 > 5):
( միավոր) n,q \le 1000, թարմացման հարցումներ չկան;
( միավոր) n,q \le 1000;
( միավոր) թարմացման հարցումներ չկան;
( միավոր) a_i \le 100, յուրաքանչյուր հարցումներում փոքր կամ հավասար է -ին;
( միավոր) n \le 10^5;
( միավոր) լրացուցիչ սահմանափակումներ չկան.