Լավ եռանկյուններ#524

Լավ եռանկյուններ

4 վայրկյան
256 մեգաբայթ
Very hard

Դուք ստանում եք կախարդական փայտիկների զանգված, որտեղ -րդ փայտիկը ունի a_i երկարություն: Մենք ասում ենք, որ փայտիկների զանգվածը լավ է, եթե գոյություն ունի երեքություն (1 \le i < j < k \le |b|), այնպես որ գոյություն ունի ոչ-դեգեներատիվ եռանկյուն, որի կողմերն են b_i, b_j և b_k:

Դուք խնդրվում եք մշակել հարցումներ երկու տեսակի:

Input

Մուտքի առաջին տողում կա երկու ամբողջ թիվ և (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).

Output

Յուրաքանչյուր տեսակի հարցման համար տպեք մեկ տող մեկ ամբողջ թիվով — առավելագույն ոչ դատարկ հարակից ենթամասերի քանակը, որոնց մեջ հատվածը կարող է բաժանվել այնպես, որ յուրաքանչյուր ենթամասը լավ լինի: Եթե հատվածը չի կարող բաժանվել ոչ դատարկ հարակից ենթամասերի, տպեք :

Examples

Example 1

Loading
Loading

Note

Սկզբնական զանգվածը 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):

Scoring

  1. ( միավոր) n,q \le 1000, թարմացման հարցումներ չկան;

  2. ( միավոր) n,q \le 1000;

  3. ( միավոր) թարմացման հարցումներ չկան;

  4. ( միավոր) a_i \le 100, յուրաքանչյուր հարցումներում փոքր կամ հավասար է -ին;

  5. ( միավոր) n \le 10^5;

  6. ( միավոր) լրացուցիչ սահմանափակումներ չկան.