[Solution] Also Try Minecraft Codeforces Solution

B. Also Try Minecraft

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 𝑛$n$, where the 𝑖$i$-th column of the world has height 𝑎𝑖$a_i$.

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

In one move, you can go from the column 𝑥$x$ to the column 𝑥−1$x-1$ or to the column 𝑥+1$x+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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 greater than the height 𝑞$q$, you get 𝑝−𝑞$p-q$ fall damage, otherwise you fly up and get 0$0$ 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 𝑛$n$ and 𝑚$m$ (2≤𝑛≤105;1≤𝑚≤105$2\le n\le {10}^5;1\le m\le {10}^5$) — the number of columns in the world and the number of quests you have to test, respectively.

Three Doors Codeforces Solution 2022

Also Try Minecraft Codeforces Solution

Recover an RBS Codeforces Solution

Rorororobot Codeforces Solution 

XOR Tree Codeforces Solution

Multiset of Strings Codeforces Solution

The second line of the input contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤109$1\le a_i\le {10}^9$), where 𝑎𝑖$a_i$ 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 𝑠𝑗$s_j$ and 𝑡𝑗$t_j$ (1≤𝑠𝑗,𝑡𝑗≤𝑛;𝑠𝑗≠𝑡𝑗$1\le s_j,t_j\le n;s_j\ne t_j$), which means you have to move from the column 𝑠𝑗$s_j$ to the column 𝑡𝑗$t_j$ during the 𝑗$j$-th quest.

Note that 𝑠𝑗$s_j$ can be greater than 𝑡𝑗$t_j$.

Output

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.