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 :
— le bâton magique à la position a changé sa longueur en ;
— imprimez le nombre maximum de sous-segments contigus non vides dans lesquels peut être partitionné de sorte que chaque sous-segment soit bon. Veuillez noter que chaque élément doit appartenir à un bon sous-segment. Si le segment ne peut pas être divisé en sous-segments contigus non vides, la réponse est .
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).
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 .
Example 1
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).
( points) n,q \le 1000, il n'y a pas de requêtes de mise à jour ;
( points) n,q \le 1000 ;
( points) il n'y a pas de requêtes de mise à jour ;
( points) a_i \le 100, pour chaque dans les requêtes, il est inférieur ou égal à ;
( points) n \le 10^5 ;
( points) pas de restrictions supplémentaires.