Maximum Non‐Overlapping Interval Pairing

You are given n segments on the number line. Each segment is represented by an interval \([l, r]\). You need to form as many pairs \((u_i, v_i)\) as possible (maximizing \(k\)) subject to the following \(k+1\) constraints:

• The segments \(u_1, u_2, \ldots, u_k\) are pairwise non‐overlapping.
• For every \(i = 1, 2, \ldots, k\), the set \[ \{v_i\} \cup \{u_j : j \neq i\} \] is pairwise non–overlapping.

Note that for each \(i\), the segments \(u_i\) and \(v_i\) must be distinct. A sufficient condition to guarantee these constraints is to form a pair \((u, v)\) such that the segment \(v\) is contained in \(u\); that is, \[ l_u \leq l_v \quad\text{and}\quad r_v \leq r_u. \]

Given this restriction, your task is to select a collection of pairs \((u_i,v_i)\) so that:

• The chosen \(u\)-segments (one from each pair) are pairwise non–overlapping.
• For every pair, there exists a partner \(v\) (different from \(u\)) which is contained in \(u\), ensuring that in every constraint the potential conflict is avoided.

Output the maximum number of pairs \(k\) that can be formed.

inputFormat

The first line contains a single integer \(n\) representing the number of segments. Each of the next \(n\) lines contains two space–separated integers \(l\) and \(r\) (with \(l \le r\)), representing the endpoints of a segment.

outputFormat

Output a single integer: the maximum number of valid pairs that can be formed.

sample

3
1 10
2 3
11 20

1