Sancho was making a road trip with his family and got really bored, so he recorded the position and initial speed of every car on the highway. For Sancho, the highway is an infinite straight line, the starting time is 0, the cars are moving points, and no car will pass another car (Sancho is very idealistic).
The cars maintain their initial speed unless they are slowed down by other cars. Car A is slowed down by car B if B started in front of A, but after a while, A reached B. When this happens, both cars move together and A's speed becomes the same as B's.
Sancho knows that there will be only a finite amount of times that a car will be slowed down by another car, and wants to know when the last slowing down will take place. If no car will be slowed down, the answer is 0.
The first line of the input contains a single integer N (1 ≤ N ≤ 105), indicating the number of cars.
N lines follow. The i-th line contains two integers Si and Vi (0 ≤ S, V ≤ 109), indicating the starting position of the i-th car and its speed. No two cars start in the same position.
Output a single decimal number - the time of the last slow down. Your answer will be considered correct if the absolute or relative error is no greater than 10 - 4.
Namely: let's assume that your answer is a, and the official answer is b. The checker program will consider your answer correct, if .
## Input
The first line of the input contains a single integer N (1 ≤ N ≤ 105), indicating the number of cars. N lines follow. The i-th line contains two integers Si and Vi (0 ≤ S, V ≤ 109), indicating the starting position of the i-th car and its speed. No two cars start in the same position.
## Output
Output a single decimal number - the time of the last slow down. Your answer will be considered correct if the absolute or relative error is no greater than 10 - 4.Namely: let's assume that your answer is a, and the official answer is b. The checker program will consider your answer correct, if .
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of guards.
Let $ Q \in \mathbb{Z}^+ $ be the number of operations.
Let $ I_i = [L_i, R_i] \subseteq \mathbb{Z} $ denote the interval of cells assigned to guard $ i $, for $ i \in \{1, \dots, N\} $.
Let $ \mathcal{I} = \{I_1, I_2, \dots, I_N\} $ be the current set of intervals.
**Constraints**
1. $ 1 \le N \le 10^5 $
2. $ 1 \le Q \le 10^5 $
3. For each interval $ [L_i, R_i] $: $ L_i \le R_i $, and $ L_i, R_i \in \mathbb{Z} $
4. Operations are of two types:
- Type 1: Update guard $ i $'s interval to $ [L, R] $
- Type 2: Query the total number of *distinct* cells covered by the union of all current intervals
**Objective**
For each query operation (type 2), compute:
$$
\left| \bigcup_{i=1}^{N} I_i \right|
$$
i.e., the cardinality of the union of all current intervals.