All Tracks Math Combinatorics Basics of Combinatorics Problem

Intersection of intervals
Tag(s):

Basics of Combinatorics, Combinatorics, Math, Medium

Problem
Editorial
Analytics

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 $$T \in S$$ and $$x, x+1 \in T$$. In particular we have that $$f(\{ [l,r] \}) = r - l$$.

Given an integer array $$A$$ of length $$2N$$. Consider a sequence of intervals $$[l_1, r_1], [l_2, r_2], \dots, [l_N, r_N]$$ valid if $$r_1 < r_2 < \dots < r_N$$, $$l_i < r_i$$ and $$(l_1, r_1, l_2, r_2, \dots, l_N, r_N)$$ is a permutation of $$A$$.

Find the sum $$f(\{ [l_1, r_1] \} \cup \{ [l_2, r_2] \} \cup \dots \cup \{ [l_N, r_N] \})$$ modulo $$10^9 + 7$$ over all possible sequences of intervals.

$$\textbf{Input}$$

The first line contains one integer - $$N (1 \le N \le 10^5)$$.

The next line contains $$2N$$ integers - $$A_1, A_2, \dots, A_{2N}$$ $$(1 \le A_1 < A_2 < \dots < A_{2N} \le 10^9)$$.

$$\textbf{Output}$$

Output the answer modulo $$10^9 + 7$$.

SAMPLE INPUT
2
1 2 3 4


SAMPLE OUTPUT
8
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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

June Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?