题目内容

在数据分析中，工程师小蓝采集了一组随时间变化的数据序列。为了衡量一段连续时间段内数据的波动程度，定义该时间段内相邻两个采集点之差的绝对值之和为“波动和”。现在小蓝需要快速回答多次关于不同时间区间的波动和查询。

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$。对于区间 $[l, r]$，其波动和定义为 $\sum_{i=l}^{r-1} |a_i - a_{i+1}|$。若区间长度为 $1$（即 $l = r$），规定波动和为 $0$。请你帮助小蓝高效地回答多次查询。

数据规模：序列长度 $n$ 与查询次数 $q$ 均不超过 $10^5$；序列中的每个数值 $a_i$ 满足 $1 \le a_i \le 10^9$；每次查询的区间 $[l, r]$ 满足 $1 \le l \le r \le n$。

输入描述

第一行包含一个正整数 $n$，表示序列的长度。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，相邻数字之间以空格分隔。