Minimum Largest Step Over Two Paths

You are given a strictly increasing integer array positions, where positions[0] = 0.

Split all indices of positions into two increasing subsequences such that:

• each subsequence includes index 0 and the last index, and
• every other index belongs to exactly one of the two subsequences.

Within a subsequence, the step between two consecutive chosen positions is the difference of their values. The cost of a subsequence is its largest step, and the cost of a split is the larger of the two subsequence costs.

Return the minimum possible cost over all valid splits.

Examples

Example 1

Input: positions = [0,2,5,6,7]
Output: 5
Explanation: Take one subsequence through positions 0, 5, 7 (steps 5 and 2)
and the other through positions 0, 2, 6, 7 (steps 2, 4, 1). The larger cost is
5, and no split does better.

Example 2

Input: positions = [0,3,9]
Output: 9
Explanation: One subsequence must step directly from 0 to 9, so its cost is 9.