该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

这是什么？算一下

时间限制：1000ms

空间限制：256MB

题目描述

给定一个具有$n$个元素的数组$a$，可以对它进行任意次如下操作：选取其中两个相邻的元素，把它们变成相反数 之后进行$m$次询问，每次询问指定一段区间$[l,r]$，请问进行任意次操作后，$a[l]+a[l+1]+...+a[r]$的值最大是多少？（每次询问之间互不影响）

输入格式

第一行包含两个整数$n,m$，表示数组的元素个数和询问次数。 第二行包含$n$个整数，代表数组$a$的元素 接下来$m$行，每行包含两个整数$l,r$，表示询问的区间

输出格式

对于每个询问，输出一行，每行一个整数，表示经过若干次操作后，$a[l]+a[l+1]+...+a[r]$的最大值

样例输入

5 3
1 5 -5 0 2
1 3
1 5
2 3

样例输出

9
13
0

数据范围

对于$40$%的数据，保证$m=1,l=1,r=n$

对于$80$%的数据，保证$l=1$

对于100%的数据，保证$n,m \le 2\times10^5,1\le l \le r\le n, -10^9\le a[i]\le 10^9$