No.2796 Small Matryoshka
Problem Statement
There are $N$ matryoshka dolls on a desk. The $i$-th matryoshka has an inner diameter of $r_i$ and an outer diameter of $R_i$. Here, $r_i\lt R_i$ holds.
Consider performing the following operations A and B, each $0$ or more times in any order, so that exactly $1$ matryoshka remains on the desk.
Operation A
- Choose distinct matryoshkas $X,Y$ on the desk and remove them from the desk. Here, the outer diameter of $X$ must be less than or equal to the inner diameter of $Y$.
- Put $X$ inside $Y$. The inner diameter of the resulting new matryoshka equals the inner diameter of $X$, and its outer diameter equals the outer diameter of $Y$.
- Place the new matryoshka on the desk.
Operation B
- Choose a matryoshka $X$ on the desk.
- Choose a real number $k\ (0\lt k\lt 1)$.
- Scale the size of $X$ by a factor of $k$. The inner and outer diameters of the resulting new matryoshka are $k$ times the original inner and outer diameters, respectively.
Find the minimum possible number of times operation B is performed.
Constraints
- All inputs are integers.
- $1\le N\le 2\times 10^5$
- $1\le r_i\lt R_i\le 10^9$
Input
$N$ $r_1$ $R_1$ $\vdots$ $r_N$ $R_N$
Output
Output the minimum possible number of times operation B is performed.
Sample
Sample 1
Input
3 1 2 2 3 1 3
Output
1
First, perform operation B to scale the size of the $3$-rd matryoshka by a factor of $0.1$.
Next, perform operation A to put the $1$-st matryoshka inside the $2$-nd matryoshka.
Finally, perform operation A to put the $3$-rd matryoshka inside the $1$-st matryoshka.
Sample 2
Input
4 6 28 2 6 82 86 62 66
Output
0
Sample 3
Input
5 6 28 6 28 6 28 6 28 6 28
Output
4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2