time limit per test
2 seconds
memory limit per test
256 megabytes
You are beta testing the new secret Terraria update. This update will add quests to the game!
Simply, the world map can be represented as an array of length nn, where the ii-th column of the world has height aiai.
There are mm quests you have to test. The jj-th of them is represented by two integers sjsj and tjtj. In this quest, you have to go from the column sjsj to the column tjtj. At the start of the quest, you are appearing at the column sjsj.
In one move, you can go from the column xx to the column x−1x−1 or to the column x+1x+1. In this version, you have Spectre Boots, which allow you to fly. Since it is a beta version, they are bugged, so they only allow you to fly when you are going up and have infinite fly duration. When you are moving from the column with the height pp to the column with the height qq, then you get some amount of fall damage. If the height pp is greater than the height qq, you get p−qp−q fall damage, otherwise you fly up and get 00 damage.
For each of the given quests, determine the minimum amount of fall damage you can get during this quest.
Input
The first line of the input contains two integers nn and mm (2≤n≤105;1≤m≤1052≤n≤105;1≤m≤105) — the number of columns in the world and the number of quests you have to test, respectively.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the height of the ii-th column of the world.
The next mm lines describe quests. The jj-th of them contains two integers sjsj and tjtj (1≤sj,tj≤n;sj≠tj1≤sj,tj≤n;sj≠tj), which means you have to move from the column sjsj to the column tjtj during the jj-th quest.
Note that sjsj can be greater than tjtj.
Output
Print mm integers. The jj-th of them should be the minimum amount of fall damage you can get during the jj-th quest completion.
Example
input
Copy
7 6 10 8 9 6 8 12 7 1 2 1 7 4 6 7 1 3 5 4 2
output
Copy
2 10 0 7 3 1
#include <iostream>
using namespace std;
int main()
{
long long n,m;
cin>>n>>m;
long long a[n+5],b[n+5],c[n+5];
cin>>a[1];
b[1]=0;
c[1]=0;
for(int i=2;i<=n;i++)
{
cin>>a[i];
if(a[i]<a[i-1])
{
b[i]=b[i-1]+a[i]-a[i-1];
}
else
{
b[i]=b[i-1];
}
if(a[i-1]<a[i])
{
c[i]=c[i-1]+a[i-1]-a[i];
}
else
{
c[i]=c[i-1];
}
}
while(m--)
{
long long x,y;
cin>>x>>y;
if(x<y)
{
cout<<b[x]-b[y]<<endl;
}
else
{
cout<<c[y]-c[x]<<endl;
}
}
return 0;
}