SP12210 HILO - High and Low

某位学生在数学课上总是感到无聊。因为老师不准他打瞌睡，所以他另辟蹊径，琢磨起黑板上数字的规律。目前，他在尝试寻找 Hi&Lo 子序列的奥秘。 简单来说，Hi&Lo 序列就是相邻数字之间差值符号相反的一个数字序列。也就是说，如果第一个数字大于第二个，那么第二个就要小于第三个，第三个又要大于第四个，以此类推。 更正式地，假设黑板上写着一组数字 $x[1], x[2], \ldots, x[n]$。从 $A$ 到 $B$ 的长度为 $k$ 的 Hi&Lo 子序列是一个索引序列 $a_1, a_2, \ldots, a_k$，必须满足以下条件： 1. $B \geq a_k > \cdots > a_2 > a_1 \geq A$ 2. 对于所有 $1 < i \leq k$，需满足 $x[a_i] - x[a_{i-1}] \neq 0$ 3. 对于所有 $1 < i < k$，需满足 $(x[a_i] - x[a_{i-1}]) (x[a_{i+1}] - x[a_i]) < 0$ 需要注意的是，任何单元素的序列也被视为 Hi&Lo 序列。 由于数字越来越多，因此找到长的子序列变得越来越有挑战性。因此，他请求你帮助编写一个程序，为他在指定区间内快速找到最长的 Hi&Lo 子序列。

输入由多个测试用例构成。每个测试用例的第一行为两个用空格分隔的整数 **N** 和 **M**（$1 \leq N \leq 100000$，$1 \leq M \leq 10000$）。第二行为 **N** 个正整数，表示黑板上的初始数字。接下来有 **M** 行，每行包含一个指令，有以下两种类型： 1. `q A B`：输出仅使用位置从 $A$ 到 $B$ 的元素所能形成的最长 Hi&Lo 子序列的长度。你可以假设 $1 \leq A \leq B \leq N$。 2. `m A B`：将序列中第 $A$ 个数修改为新的正整数 $B$。你可以假设 $1 \leq A \leq N$。 黑板上的数字都不会超过 $10^9$。每个测试用例后应输出一个空行。输入的最后一行是两个零，表示输入结束。

对于每个类型为 1 的指令，输出一行结果，表示该查询的答案。每个测试用例结束后输出一个空行。 **本翻译由 AI 自动生成**