Bons triangles#524

Bons triangles

4 secondes
256 mégaoctets
Very hard

On vous donne un tableau de bâtons magiques , où le bâton -ème a une longueur a_i. On appelle un tableau de bâtons bon, s'il existe un triplet (1 \le i < j < k \le |b|), tel qu'il existe un triangle non dégénéré avec des côtés b_i, b_j et b_k.

Vous devez traiter requêtes de deux types :

Input

La première ligne de l'entrée contient deux entiers et (1 \le n,q \le 5 \cdot 10^5) — longueur du tableau de bâtons magiques et nombre de requêtes.

La deuxième ligne de l'entrée contient entiers a_i (1 \le a_i \le 10^6) — longueurs des bâtons magiques dans le tableau .

Chacune des lignes suivantes contient une requête d'un des types suivants :

  • (1 \le i \le n, 1 \le x \le 10^6) ;

  • (1 \le l \le r \le n).

Output

Pour chaque requête de type , imprimez une seule ligne avec un seul entier — le nombre maximum de sous-segments contigus non vides dans lesquels le segment peut être partitionné de sorte que chaque sous-segment soit bon. Si le segment ne peut pas être divisé en sous-segments contigus non vides, imprimez .

Examples

Example 1

Loading
Loading

Note

Le tableau initial est a = [1, 3, 5, 4, 7, 5, 4, 3, 9, 8].

Requête "2 1 10": Nous pouvons partitionner l'ensemble du tableau en bons sous-segments : [1, 3, 5, 4], [7, 5, 4], [3, 9, 8].

  • [1, 3, 5, 4] est bon : les bâtons de longueur , , forment un triangle (3 + 4 > 5).

  • [7, 5, 4] est bon : les bâtons de longueur , , forment un triangle (4 + 5 > 7).

  • [3, 9, 8] est bon : les bâtons de longueur , , forment un triangle (3 + 8 > 9).

Requête "1 3 3": Le tableau devient a = [1, 3, 3, 4, 7, 5, 4, 3, 9, 8].

Requête "2 1 10": Nous pouvons partitionner l'ensemble du tableau en bons sous-segments : [1, 3, 3], [4, 7, 5], [4, 3, 9, 8].

  • [1, 3, 3] est bon : les bâtons de longueur , , forment un triangle (1 + 3 > 3).

  • [4, 7, 5] est bon : les bâtons de longueur , , forment un triangle (4 + 5 > 7).

  • [4, 3, 9, 8] est bon : les bâtons de longueur , , forment un triangle (4 + 8 > 9).

Requête "2 1 7": Le sous-tableau est [1, 3, 3, 4, 7, 5, 4]. Nous pouvons le partitionner en bons sous-segments : [1, 3, 3] et [4, 7, 5, 4].

  • [1, 3, 3] est bon : 1 + 3 > 3.

  • [4, 7, 5, 4] est bon : les bâtons de longueur , , forment un triangle (4 + 4 > 5).

Requête "2 3 8": Le sous-tableau est [3, 4, 7, 5, 4, 3]. Nous pouvons le partitionner en bon sous-segment : [3, 4, 7, 5, 4, 3].

  • [3, 4, 7, 5, 4, 3] est bon : les bâtons de longueur , , forment un triangle (3 + 4 > 5).

Scoring

  1. ( points) n,q \le 1000, il n'y a pas de requêtes de mise à jour ;

  2. ( points) n,q \le 1000 ;

  3. ( points) il n'y a pas de requêtes de mise à jour ;

  4. ( points) a_i \le 100, pour chaque dans les requêtes, il est inférieur ou égal à ;

  5. ( points) n \le 10^5 ;

  6. ( points) pas de restrictions supplémentaires.