Final Interval Possibilities

Professor Pang has a multiset of intervals \(S = \{[l_i, r_i]\}\) (with \(l_i < r_i\)). He will perform the following operation exactly \(|S| - 1\) times:

• Select two intervals \([a,b]\) and \([c,d]\) in \(S\), and then choose two integers \(x\) and \(y\) such that \(x \in [a,b]\), \(y \in [c,d]\) and \(x < y\); then remove \([a,b]\) and \([c,d]\) from \(S\) and add the new interval \([x,y]\) to \(S\).

After doing this repeatedly, only one final interval remains — which Professor Pang receives as a gift.

Your task is to calculate the number of different final intervals (i.e. the number of distinct pairs \([x,y]\) with \(x < y\)) that can be obtained by choosing different sequences of operations and different choices of \(x\) and \(y\) in each merge.

Note: In every merge operation, the two chosen intervals must be different (so that the two endpoints come from two distinct intervals resulting eventually in different "branches" of the merge tree). In particular, if the input contains only one interval, then no merge is performed and the final interval is exactly the given one.

---

Observation and Explanation:

Consider that in each merge the new interval \([x,y]\) is constructed by choosing \(x\) from one interval and \(y\) from another – with \(x < y\). One may show that the final interval always has its left endpoint coming from some original interval and its right endpoint coming from some other original interval (or from different branches in later merges). In other words, a final interval \([x,y]\) is achievable if and only if there exist two (not necessarily distinct as sets, but coming from different merge branches) original intervals and integers \(x\) and \(y\) with:

[ \begin{aligned} &x \in [l_i, r_i] \quad \text{for some } i,\[1mm] &y \in [l_j, r_j] \quad \text{for some } j \quad (i \neq j),\[1mm] &x < y. \end{aligned} ]

Let \(U\) be the set of all integers that lie in at least one of the intervals in \(S\). If we could choose \(x\) and \(y\) arbitrarily from \(U\) (with \(x < y\)), the total number of choices would be \(\binom{|U|}{2}\). However, if a point \(v \in U\) is covered uniquely by an interval (i.e. it comes from exactly one interval), then choosing both \(x\) and \(y\) from the same unique interval is not allowed (because then the two endpoints come from the same original interval, and such a merge is impossible).

If for each interval \(i\) we let \(u_i\) be the number of integers that are exclusively covered by interval \(i\) (and by no other interval), then the number of pairs \((x,y)\) taken entirely from this interval is \(\binom{u_i}{2}\) and these must be removed from \(\binom{|U|}{2}\).

Thus, for \(|S| \ge 2\) the answer is given by:

[ \text{Answer} = \binom{|U|}{2} - \sum_{i=1}^{n} \binom{u_i}{2}. ]

For the case \(n=1\) (i.e. when there is only one interval), there is no merge so the only final interval is the original one; output 1 in that case.

---

Input Format:

The first line contains an integer \(n\) (the number of intervals).
Then \(n\) lines follow; each line contains two integers \(l_i\) and \(r_i\) (with \(l_i < r_i\)), representing an interval \([l_i, r_i]\).

Output Format:

Output a single integer: the number of different final intervals Professor Pang can get.

inputFormat

The first line contains an integer \(n\) (with \(1 \le n \le 10^5\) in typical constraints). Each of the next \(n\) lines contains two space-separated integers \(l_i\) and \(r_i\) (with \(l_i < r_i\)). All endpoints are integers; the intervals are inclusive, i.e. an interval \([l_i, r_i]\) contains all integers \(x\) with \(l_i \le x \le r_i\).

outputFormat

Output a single integer: the number of different final intervals that may be obtained. (For \(n = 1\), output 1.)

Note: It is guaranteed that the answer fits in a 64-bit integer.

sample

2
1 3
2 4

6