7 30 s 128 MB
You want to cycle to a programming contest. The shortest route to the contest might be over the tops of some mountains and through some valleys. From past experience you know that you perform badly in programming contests after experiencing large differences in altitude. Therefore you decide to take the route that minimizes the altitude difference, where the altitude difference of a route is the difference between the maximum and the minimum height on the route. Your job is to write a program that finds this route.
You are given:
Your program must find the route that minimizes the altitude difference between the highest and the lowest point on the route. If there are multiple possibilities, choose the shortest one.
In this case the shortest path from 1 to 7 would be through 2, 3 and 4, but the altitude difference of that path is 8. So, you prefer to go through 5, 6 and 4 for an altitude difference of 2. (Note that going from 6 directly to 7 directly would have the same difference in altitude, but the path would be longer!)
On the first line an integer $t (1 \leq t \leq 100)$: the number of test cases.
Then for each test case:
You may assume that the altitude on a road between two crossings changes linearly.
You start at crossing $1$ and the contest is at crossing $n$. It is guaranteed that it is possible to reach the programming contest from your home.
For each testcase, output one line with two integers separated by a single space:
1 7 9 4 9 1 3 3 5 4 1 2 1 2 3 1 3 4 1 4 7 1 1 5 4 5 6 4 6 7 4 5 3 2 6 4 2