4493: 饮水计划

Nanarikom 在努力练习多喝水。

非常惭愧，尽管独立生活了这么多年，Nanarikom 仍然没有办法很好地照顾自己。Nanarikom 制定了喝水计划，下定决心要改变这一现状。

对于连续的 $m$ 天，假设长度为 $m$ 的序列 b_1, b_2, \dots, b_mb1,b2,…,bm 表示第 $i$ 天的喝水量为 b_ibi 单位。如果存在 $1\le k<m$ 使得 \max_{i=1}^{k} b_i \leq \min_{i=k+1}^{m} b_imaxi=1kbi≤mini=k+1mbi，则 Nanarikom 认为 $k$ 是 $b$ 序列上的一个 milestone。Nanarikom 记函数 $f(b)$ 表示 $b$ 序列上 milestone 的数量，以此衡量自己的进步。

现在，Nanarikom 已经记录了自己连续 $n$ 天的实际喝水量 a_1, a_2, \dots, a_na1,a2,…,an。Nanarikom 想进行 $q$ 次询问，第 $i$ 次询问给定 l_i, r_ili,ri 查询 f(a[l_i;r_i])f(a[li;ri]) 的值。其中，记号 $a[l;r]$ 表示 $a$ 在区间 $[l,r]$ 上的子段 a_l, a_{l+1}, a_{l+2}, \dots, a_ral,al+1,al+2,…,ar。

你需要回答 Nanarikom 的 $T$ 组询问。