There are n cities labeled 0 through n - 1. Initially, a one-way road goes from each city i to city i + 1, so the cities form a directed chain.
Process queries in order. Each pair [u, v] adds a one-way road from city u to city v. Added roads remain available for all later queries.
After each addition, find the minimum number of roads needed to travel from city 0 to city n - 1. Return these distances in query order.
Example 1:
Input: n = 6
queries = [[1,4],[0,3],[0,5]]
Output: [3,3,1]Explanation: The shortest routes can be 0 → 1 → 4 → 5 (3 roads), then 0 → 3 → 4 → 5 (still 3 roads), then the direct road 0 → 5 (1 road).
Example 2:
Input: n = 5
queries = [[0,4],[1,3]]
Output: [1,1]Explanation: The first added road goes directly from city 0 to city 4, giving distance 1. Adding 1 → 3 cannot improve on a direct road, so the second distance is also 1.
Example 3:
Input: n = 6
queries = [[0,2],[2,5],[1,5]]
Output: [4,2,2]Explanation: After adding 0 → 2, a shortest route has 4 roads. The next query adds 2 → 5, which combines with the earlier addition to give 0 → 2 → 5 in 2 roads. Adding 1 → 5 leaves the best distance at 2.
Constraints:
3 <= n <= 5001 <= queries.length <= 500queries[i].length == 20 <= queries[i][0] < queries[i][1] < nqueries[i][1] - queries[i][0] > 1- No road appears more than once among the queries.