<p>There are <code>n</code> cars traveling at different speeds in the same direction along a one-lane road. You are given an array <code>cars</code> of length <code>n</code>, where <code>cars[i] = [position<sub>i</sub>, speed<sub>i</sub>]</code> represents:</p>

<ul>
	<li><code>position<sub>i</sub></code> is the distance between the <code>i<sup>th</sup></code> car and the beginning of the road in meters. It is guaranteed that <code>position<sub>i</sub> &lt; position<sub>i+1</sub></code>.</li>
	<li><code>speed<sub>i</sub></code> is the initial speed of the <code>i<sup>th</sup></code> car in meters per second.</li>
</ul>

<p>For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the <strong>slowest</strong> car in the fleet.</p>

<p>Return an array <code>answer</code>, where <code>answer[i]</code> is the time, in seconds, at which the <code>i<sup>th</sup></code> car collides with the next car, or <code>-1</code> if the car does not collide with the next car. Answers within <code>10<sup>-5</sup></code> of the actual answers are accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cars = [[1,2],[2,1],[4,3],[7,2]]
<strong>Output:</strong> [1.00000,-1.00000,3.00000,-1.00000]
<strong>Explanation:</strong> After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cars = [[3,4],[5,4],[6,3],[9,1]]
<strong>Output:</strong> [2.00000,1.00000,1.50000,-1.00000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= cars.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= position<sub>i</sub>, speed<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
	<li><code>position<sub>i</sub> &lt; position<sub>i+1</sub></code></li>
</ul>

class Solution:
    def getCollisionTimes(self, A):
        """
        Also seems like we should iterate in reverse.
        
        Only care about consecutive fleets: if a car catches up to the fleet in front of it, it's bounded by that fleet's speed.
        
        if speed[i] <= min(speed[i+1]):
            res[i] = -1

        Next: it's a bit confusing, since we need to know when the previous car caught up with the previous fleet, and so on. There are a few cases we should care about:
            
        car[i] catches up with car[i+1] before it merges: can compute when they merge
        
            pos[i] + t1 * speed[i] = pos[i+1] + t[i] * speed[i+1]
        =>  pos[i+1] - pos[i] = t[i] (speed[i] - speed[i+1])
        
        What if t[i] > t[i+1] > -1?
        This is tricky => naive is O(n^2), since we might have to look over all previous cars.
        
        [4, 0], [2, 4], [1, 5] =>
        
        time 1: 
        [8, 0], [4, 4], [2, 6], [1, 6] => the first fleet, moving at speed 1, formed at time t = 1.
        
        Therefore: car[0] merges into fleet[1] before t = 2.
        
        Thus: we care about when cars[i+1] merges + which speed it's going at.
        
        Naively: we could track every time t such that a car merges, then do some math.
        O(n^2)
        
        O(n): iterate forward?
        
        t[i] := the time it takes for car[i] to crash into the car before it, assuming NO other constraints.
        
        NO: SHOULD HAVE SEEN THAT we only care about the first car it crashes with.
        O(n^2) naively. Can we do better?
        
        [4, 0], [2, 4], [1, 5]
        - All cars crash with [1, 5].
        
        How to know which it will crash with first?
        
        pos[j] - pos[i] = t[i] (speed[i] - speed[j])
        
        t[i] = (pos[j] - pos[i]) / (speed[i] - speed[j])
        
        Monotone stack?
        Let's say that we have a monotone decreasing stack in speed.
        
        [1, 2, 4]
        
        If 8 can't catch up with 4, can it catch up with 2 or 1 before 4?
        
        
        """
        stack = []
        n = len(A)
        res = [-1] * n
        for i in range(n-1, -1, -1):
            p, s = A[i]
            while stack and (s <= A[stack[-1]][1] or (A[stack[-1]][0] - p) / (s - A[stack[-1]][1]) >= res[stack[-1]] > 0):
                stack.pop()
            if stack:
                res[i] = (A[stack[-1]][0] - p) / (s - A[stack[-1]][1])
            stack.append(i)
        return res
993