406469: GYM102419 B Super Jaber

Jaber is a superhero, he always helps people who are in trouble.

He lives in a city described as a sequence of $$$n$$$ consecutive buildings, the height of the $$$i_{th}$$$ buildings is $$$h_i$$$. The floors are numbered starting from the ground floor $$$0$$$ and ending with the last floor $$$h_i$$$.

Jaber will do $$$m$$$ missions, in the $$$i_{th}$$$ mission he will be at the $$${i_1}^{th}$$$ building on the $$${f_1}^{th}$$$ floor, and he has to save someone in the $$${i_2}^{th}$$$ building on the $$${f_2}^{th}$$$ floor.

In one move Jaber can do one of these movements.

1- If Jaber is not at the ground floor he can go down (from the $$$i_{th}$$$ floor to the $$${i - 1}_{th}$$$ floor).

2- If Jaber is not on the last floor, he can go up (from the $$$i_{th}$$$ floor to the $$${i + 1}_{th}$$$ floor).

3- If Jaber is on the ground floor he can go to the ground floor of any of the adjacent buildings.

4- If Jaber is on the last floor he can go to the last floor of any adjacent buildings if the height of that building is strictly less than the current building height.

As a super-hero, Jaber has a superpower, Jaber can choose any segment of consecutive building and decrease their heights by a non-negative integer $$$l$$$, but he should satisfy some rules:

1- $$$l$$$ should be strictly less than the heights of all buildings in the chosen segment.

2- The starting and the ending buildings ($$$i_1$$$ and $$$i_2$$$) mustn't be included in the chosen segment.

3- The value of $$$l$$$ is bounded by an integer $$$k$$$,$$$(1 \leq l \leq k)$$$. Since Jaber's power is limited, after every mission the buildings will return to their original height.

Now you should tell Jaber for every mission what is the minimum possible time to reach the $$${f_2}^{th}$$$ floor in $$${i_2}^{th}$$$ building from the $$${f_1}^{th}$$$ floor in th $$${i_1}^{th}$$$ building.

The first line of input contains two integers $$$n$$$ and $$$m$$$ which are the number of buildings and the number of missions $$$(2 \leq n \leq 2 \times 10 ^ {5})$$$ $$$(1 \leq m \leq 2 \times 10 ^ {5})$$$.

The next line contains $$$n$$$ integers, the $$$i_{th}$$$ one is $$$h_i$$$, which is the height of the $$$i_{th}$$$ building $$$(1 \leq h_i \leq 5 \times 10 ^ {8})$$$.

For the next $$$m$$$ lines, every line will contain five integers $$$i_1$$$ $$$f_1$$$ $$$i_2$$$ $$$f_2$$$ $$$k$$$ $$$(1 \leq i_1 , i_2 \leq n)$$$ $$$(i_1 \neq i_2)$$$ $$$(0 \leq f_1 \leq h_{i_1})$$$ $$$(0 \leq f_2 \leq h_{i_2})$$$ $$$(1 \leq k \leq 5 \times 10 ^ {8})$$$ , which the description of every mission.

Print $$$m$$$ lines, the $$$i_{th}$$$ should be the answer of the $$$i_{th}$$$ mission.

4 1
10 5 9 12
1 10 3 0 4

3