Clash finder: hints, no solution

A clinic front desk exports a day of appointments as a list of [start, end) pairs, in minutes after midnight, in no particular order. An appointment that starts exactly when another ends does not clash with it.

Sort the appointments by start time, breaking ties by their position in the list. Go through them in that order and find the first appointment that starts before the previous one in that order has ended. Return the list positions (counting from 0) of that appointment and the previous one, with the smaller position first. If nothing clashes, return an empty list.

Examples

Input

appointments = [[540, 600], [560, 570], [610, 650]]

Output

[0, 1]

Note

The 560 appointment starts before the 540 to 600 one has ended, and it is the first such appointment in time order.

Input

appointments = [[540, 600], [600, 660], [660, 700]]

Output

[]

Note

Every appointment starts exactly when the previous one ends, which is not a clash.

Input

appointments = [[300, 360], [100, 200], [150, 210], [400, 420]]

Output

[1, 2]

Note

In time order the 100 to 200 appointment comes first and 150 to 210 starts before it ends; their list positions are 1 and 2.

Constraints

• 0 <= appointments.length <= 120000
• 0 <= start < end <= 1000000 for every appointment
• Appointments may be given in any order and may repeat

Hint 1: a nudge

If the appointments were laid out in time order, what would you have to compare to notice a clash? How many neighbours does each appointment need to be checked against?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing