# [Solution] Also Try Minecraft solution codeforces

Also Try Minecraft solution codeforces – You are beta testing the new secret Terraria update. This update will add quests to the game!

## [Solution] Also Try Minecraft solution codeforces

Simply, the world map can be represented as an array of length 𝑛n, where the 𝑖i-th column of the world has height 𝑎𝑖ai.

There are 𝑚m quests you have to test. The 𝑗j-th of them is represented by two integers 𝑠𝑗sj and 𝑡𝑗tj. In this quest, you have to go from the column 𝑠𝑗sj to the column 𝑡𝑗tj. At the start of the quest, you are appearing at the column 𝑠𝑗sj.

In one move, you can go from the column 𝑥x to the column 𝑥1x−1 or to the column 𝑥+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 𝑝p to the column with the height 𝑞q, then you get some amount of fall damage. If the height 𝑝p is greater than the height 𝑞q, you get 𝑝𝑞p−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.

## [Solution] Also Try Minecraft solution codeforces

The first line of the input contains two integers 𝑛n and 𝑚m (2𝑛105;1𝑚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 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109), where 𝑎𝑖ai is the height of the 𝑖i-th column of the world.

The next 𝑚m lines describe quests. The 𝑗j-th of them contains two integers 𝑠𝑗sj and 𝑡𝑗tj (1𝑠𝑗,𝑡𝑗𝑛;𝑠𝑗𝑡𝑗1≤sj,tj≤n;sj≠tj), which means you have to move from the column 𝑠𝑗sj to the column 𝑡𝑗tj during the 𝑗j-th quest.

Note that 𝑠𝑗sj can be greater than 𝑡𝑗tj.

## [Solution] Also Try Minecraft solution codeforces

Print 𝑚m integers. The 𝑗j-th of them should be the minimum amount of fall damage you can get during the 𝑗j-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