Intersection of intervals

4

18 votes
Combinatorics, Math, Medium
Problem

Let S be a set of intervals of integers and f(S) be the number of integers x for which there exist an interval T with TS and x,x+1T. In particular we have that f({[l,r]})=rl.

Given an integer array A of length 2N. Consider a sequence of intervals [l1,r1],[l2,r2],,[lN,rN] valid if r1<r2<<rN, li<ri and (l1,r1,l2,r2,,lN,rN) is a permutation of A.

Find the sum f({[l1,r1]}{[l2,r2]}{[lN,rN]}) modulo 109+7 over all possible sequences of intervals.

Input

The first line contains one integer - N(1N105).

The next line contains 2N integers - A1,A2,,A2N (1A1<A2<<A2N109).

Output

Output the answer modulo 109+7.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

The valid intervals are {([1,2],[3,4]),([1,3],[2,4]),([2,3],[1,4])} contributing with 2,3,3 respectively to the answer.

Editor Image

?