Optimal Band Performance Schedule

You are given a list of bands, each with a unique identifier band_id and a performance_time. Your task is to rearrange the bands to minimize the maximum gap between consecutive performance times when they are scheduled in a linear order.

Let the performance times after scheduling be \(t_1, t_2, \ldots, t_n\). The maximum gap is defined as:

\(\max_{1 \leq i < n} (t_{i+1} - t_i)\).

You need to find an ordering of band identifiers that minimizes this value. The intended strategy is to first sort the bands by their performance times, and then construct an order using a two-pointer technique: one pointer starting from the beginning (smallest time) and the other from the end (largest time), alternating between them.

inputFormat

The input is read from standard input. The first line of input contains a single integer n, the number of bands. Each of the following n lines contains two space-separated integers representing band_id and performance_time of a band.

outputFormat

Output the rearranged order of band identifiers on one line, separated by spaces. This order is computed to minimize the maximum gap between consecutive performance times.

4
1 30
2 45
3 35
4 50

1 4 3 2