Minimizing Sum of Pairwise Absolute Differences with Interval Constraints

Cirno has \( n \) integers \( a_1,a_2,\dots,a_n \) with corresponding constraint pairs \( (l_i, r_i) \). You are asked to choose each \( a_i \) such that \( a_i \in [l_i, r_i] \) in order to minimize the objective

[ \min_{\forall t,; a_t \in [l_t,r_t]} \left{ \sum_{i=1}^{n}\sum_{j=1}^{n}|a_i-a_j| \right} ]

The optimal strategy is to make the values as equal as possible. In other words, you can choose a common value \( v \) and set

[ a_i = \begin{cases} ; l_i, & \text{if } v < l_i,\ ; v, & \text{if } v \in [l_i,r_i],\ ; r_i, & \text{if } v > r_i. \end{cases} ]

Your task is to compute the minimum possible sum of pairwise absolute differences achievable using this strategy.

inputFormat

The first line contains a single integer \( n \) representing the number of integers. The next \( n \) lines each contain two integers \( l_i \) and \( r_i \) denoting the lower and upper bounds for \( a_i \), respectively.

outputFormat

Output a single integer representing the minimum possible sum of pairwise absolute differences when each \( a_i \) is chosen from \( [l_i, r_i] \).

sample

3
1 3
2 2
3 5

4