Bob, a railway enthusiast, is excited about the city's new train line. However, he finds the planned service too slow and has devised his own proposal to improve travel times.

In Bob's proposal, the train line consists of $$$N$$$ stations numbered sequentially from $$$1$$$ to $$$N$$$. Every train station will have an integer level $$$A_i$$$, where $$$1 \le A_i \le M$$$. There will also be $$$M$$$ train types numbered from $$$1$$$ to $$$M$$$. A train of type $$$j$$$ stops only at stations $$$i$$$ where the station's level $$$A_i \le j$$$. All trains travel only in the direction of increasing station numbers.

Figure 1: An example of $$$4$$$ train types. In this example, a train of type $$$2$$$ stops at stations $$$3$$$, $$$4$$$, $$$6$$$ and $$$9$$$ in order.

The time to travel between any two consecutive stops on any train's route is exactly $$$1$$$ minute. Passengers can also switch between different train types at any station. These transfers are instantaneous, with no waiting time. In the example below, travelling from station $$$2$$$ to station $$$7$$$ takes $$$4$$$ minutes.

Figure 2: Travelling from station $$$2$$$ to station $$$7$$$.

Now, Bob wants to test the effectiveness of his proposal. He has collected data for $$$Q$$$ potential passenger trips. For each trip $$$i$$$, from a starting station $$$U_i$$$ to a destination station $$$V_i$$$, your task is to calculate the minimum possible travel time under his proposal.