Chef and Triangles

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is long been involved in cooking recipes. He has now got bored with it, and has to decided to play with food instead of cooking it up.
He has already selected N spaghetti strands for his dish. He has to select just one extra strand such that this strand's length makes a nondegenerate triangle with some of the two other strands already present in the dish. A triangle formed by three collinear points is called a degenerate triangle. The length of the strand to be selected must be an integer in the range [L, R] (both inclusive).
Formally, let array L denote the lengths of N strands, then the extra strand of length X can be selected if there exists two different indices i, j (i ≠ j) such that there can be made a triangle of side lengths L_{i}, L_{j} and X.
Can you help him find the number of possible valid lengths of the extra strand?
Note again that three collinear points are not considered to form a triangle.
Input
First line of the input contains three space separated N, L and R, denoting the number of strands already present in the dish and the range of the length of the new strand to be selected respectively.
The next line contains N space separated integers, where the ith integer L_{i} denotes the length of the ith strand.
Output
Output a single line corresponding to the answer of the problem.
Constraints
 2 ≤ N ≤ 10^{6}
 1 ≤ L ≤ R ≤ 10^{18}
 1 ≤ L_{i} ≤ 10^{18}
Subtasks
Subtask #1 (10 points):
 2 ≤ N ≤ 100
 1 ≤ L ≤ R ≤ 10^{6}
Subtask #2 (30 points):
 2 ≤ N ≤ 1000
 1 ≤ L ≤ R ≤ 10^{18}
Subtask #3 (60 points):
 2 ≤ N ≤ 10^{6}
 1 ≤ L ≤ R ≤ 10^{18}
Example
Input: 5 1 4 1 2 3 4 5 Output: 3
Explanation
If Chef chooses the strand of length 1, he can't form a triangle using this strand and the any of the pair of strands of length 1, 2, 3, 4, 5. However, for each of the extra strand of length 2, 3, 4, one can find at least one pair of strands such that those pair of strands and the extra strand makes a triangle. So, the answer will be 3.
Author:  kevind 
Tester:  mgch 
Editorial  https://discuss.codechef.com/problems/MAKETRI 
Tags  kevind, maths, stl 
Date Added:  14012017 
Time Limit:  1  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions