Overview

Given \(N\) buses whose arrival times are provided in ascending order, we examine all differences between consecutive arrival times (arrival intervals) and find their minimum and maximum values.

Analysis

The arrival intervals between consecutive pairs of buses are exactly the \(N-1\) values \(T_{i+1} - T_i \ (1 \le i \le N-1)\) for the arrival time sequence \(T_1 < T_2 < \cdots < T_N\).

The key point here is that the problem explicitly states “consecutive” pairs.
If we had to consider “the interval between any two buses,” we would need to check all combinations, resulting in \(O(N^2)\), which is far too slow for \(N \le 2\times 10^5\) (approximately \(4\times 10^{10}\) pairs).

However, since this problem only considers consecutive pairs, all we need to do is compute the differences between adjacent elements in order. For example, if
\(T = [10, 40, 55, 100]\), the intervals are \([30, 15, 45]\), and the answer is minimum \(15\), maximum \(45\).

Algorithm

1. Read the time sequence \(T\) from input (already strictly monotonically increasing).
2. For \(i=2\) to \(N\), compute the difference \(d = T_i - T_{i-1}\).
3. Update the minimum mn and maximum mx of the differences \(d\).
4. Finally, output mn mx.

Since we only look at each adjacent difference once, this completes in a single pass.

Complexity

• Time complexity: \(O(N)\) (computing the difference \(N-1\) times)
• Space complexity: \(O(N)\) (for storing the time sequence; if only differences are needed, \(O(1)\) is also possible)

Implementation Notes

• Initialize mn with a sufficiently large value (e.g., \(10^{18}\)) and mx with 0 for easy updating.

• Since the input size can be up to \(2\times 10^5\), in Python using sys.stdin.buffer.read() to read all input at once is faster.

• Since the differences are always positive (\(T_{i} > T_{i-1}\)), the minimum and maximum updates can be written straightforwardly.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    t = data[1:1+n]

    mn = 10**18
    mx = 0
    prev = t[0]
    for i in range(1, n):
        d = t[i] - prev
        if d < mn:
            mn = d
        if d > mx:
            mx = d
        prev = t[i]

    sys.stdout.write(f"{mn} {mx}\n")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.