Minimum Number of Liars in Exam

There are \(n\) people taking an exam. Some scores may be equal. The \(i\)th person says: "There are \(a_i\) people who scored higher than me and \(b_i\) people who scored lower than me." Note that when scores are equal, they are not considered as higher or lower.

Your task is to determine the minimum number of people who must be lying.

A person telling the truth must satisfy the following condition: if we partition the \(n\) participants into groups (according to their scores in nonincreasing order) with possible ties, and if a person is in a group positioned at index \(j\) (starting from \(j=1\)), then the number of people with strictly higher scores is \(\sum_{k=1}^{j-1} x_k\) where \(x_k\) is the size of group \(k\), and the number of people with strictly lower scores is \(n-\sum_{k=1}^{j} x_k\). Consequently, a truthful person in group \(j\) must have \[ a_i=\sum_{k=1}^{j-1} x_k, \quad b_i = n-\sum_{k=1}^{j} x_k, \quad \text{and} \quad x_j=n-a_i-b_i. \]

You are allowed to choose any arrangement (i.e. any grouping into groups with positive sizes that sum to \(n\)) and designate a subset of people as truthful, provided their claims exactly match the corresponding numbers. Determine the minimum number of liars (i.e. the people whose claims cannot be consistent with any arrangement).

inputFormat

The first line contains an integer \(n\) \((1 \le n \le 10^5)\), representing the number of participants. Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\) \((0\le a_i,b_i\le n)\), representing the claim of the \(i\)th person that there are \(a_i\) people with scores higher than him and \(b_i\) people with scores lower than him.

It is guaranteed that the input size is large so you should consider efficient algorithms.

outputFormat

Output a single integer, the minimum number of liars.

sample

3
0 2
1 1
2 0

0