Like any unknown mathematician, Yuri has favourite numbers: $A$, $B$, $C$, and $D$, where $A \leq B \leq C \leq D$. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides $x$, $y$, and $z$ exist, such that $A \leq x \leq B \leq y \leq C \leq z \leq D$ holds?

Yuri is preparing problems for a new contest now, so he is very busy. That's why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.


-----Input-----

The first line contains four integers: $A$, $B$, $C$ and $D$ ($1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^5$) — Yuri's favourite numbers.


-----Output-----

Print the number of non-degenerate triangles with integer sides $x$, $y$, and $z$ such that the inequality $A \leq x \leq B \leq y \leq C \leq z \leq D$ holds.


-----Examples-----
Input
1 2 3 4

Output
4

Input
1 2 2 5

Output
3

Input
500000 500000 500000 500000

Output
1



-----Note-----

In the first example Yuri can make up triangles with sides $(1, 3, 3)$, $(2, 2, 3)$, $(2, 3, 3)$ and $(2, 3, 4)$.

In the second example Yuri can make up triangles with sides $(1, 2, 2)$, $(2, 2, 2)$ and $(2, 2, 3)$.

In the third example Yuri can make up only one equilateral triangle with sides equal to $5 \cdot 10^5$.

Difficulty: interview

Starter code:

Solutions:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    a, b, c, d = nm()
    m = 10**6 + 10
    l = [0]*m
    for i in range(a, b+1):
        l[i+b] += 1
        l[i+c+1] += -1
    for i in range(m-1):
        l[i] += l[i-1]
    for i in range(m-2, -1, -1):
        l[i] += l[i+1]
    print(sum(l[i+1] for i in range(c, d+1)))
    return

solve()

# T = ni()
# for _ in range(T):
#     solve()


def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


a, b, c, d = read_ints()
ans = 0
m = min(c - b, d - c)
n = max(c - b, d - c)
for delta in range(d - b + 1):
    right = 0
    if delta <= m:
        right = delta + 1
    elif delta <= n:
        right = m + 1
    else:
        right = d - b - delta + 1
    left = max(0, b - max(delta + 1, a) + 1)
    ans += left * right
print(ans)


a, b, c, d = map(int, input().split())

ans = 0

ru = [0] * (10 ** 6 + 10)
for x in range(a, b + 1):
    l = x + b
    r = x + c + 1
    ru[l] += 1
    ru[r] -= 1
for i in range(10 ** 6 + 9):
    ru[i + 1] += ru[i]

for i in range(10 ** 6 + 9):
    ru[i + 1] += ru[i]

ans = 0
for z in range(c, d + 1):
    ans += ru[-1] - ru[z]

print(ans)

def cnt(x) :
	return x * (x + 1) // 2
t = 1
while t > 0:
	t -= 1
	a, b, c, d = map(int, input().split())
	ans = 0
	for x in range(a, b + 1) :
		l, r = x + b, x + c
		ans += cnt(min(r, d) - c) - cnt(max(min(l - 1, d) - c, 0))
		ans += max(0, r - max(d, l - 1)) * (d - c + 1)
	print(ans)

import sys

def solve():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    ans = 0
    fib = [0] * (D + 1)
    fib[1] = 1
    for i in range(2, D + 1): 
        if i <= C - B + 1: fib[i] = fib[i-1] + i
        else: fib[i] = fib[i-1] + (C - B + 1)
    for z in range(C, D + 1):
        if B + C <= z: continue
        else:
            xlow = z - C + 1
            pN = B - xlow + 1
            psubN = A - xlow
            if xlow >= A: ans += fib[pN]
            else: ans += fib[pN] - fib[psubN]

    print(ans)

    return 0

def __starting_point():
    solve()
__starting_point()

import sys

input = sys.stdin.readline


def sum1(x):
	k = min(d, c + x - 1, b + x - 1)
	if k < c:
		return 0
	else:
		return (c - b + 1) * (k - c + 1)

def sum2(x):
	k = min(d, c + x - 1)
	l = max(b + x, c)
	if k < l:
		return(0)
	else:
		return (c + x) * (k - l + 1) - (k + l) * (k - l + 1) // 2

a, b, c, d = list(map(int, input().split()))
res = 0
for x in range(a, b + 1):
	res += sum1(x) + sum2(x)
print(res)


import sys
input = sys.stdin.readline

A,B,C,D=list(map(int,input().split()))

def sm2(x,A,B,C):
    MIN=A+B
    MAX=B+C
    fr=min(B-A,C-B)

    sa=min(x-MIN,MAX-x,fr)

    return sa+1

def calc(x,C,D):
    return max(0,min(x-1,D)-C+1)

ANS=0
for x in range(A+B,B+C+1):
    smplus=sm2(x,A,B,C)
    ANS+=smplus*calc(x,C,D)

    #print(x,smplus,ANS)

print(ANS)

    


a,b,c,d=map(int,input().split())
sol=0
z=c
sm=min(c-b,b-a)
bg=max(c-b,b-a)
while b+c>=z and z<=d:
    mn=a+b
    m1=mn+sm
    mx=b+c
    m2=mx-sm
    maxi=(sm+1)*(bg+1)
    if mn>z:
        sol+=maxi
    if mn<=z and m1>z:
        foo=z+1-mn
        sol+=maxi
        sol-=((foo)*(foo+1))//2
    if m1<=z and m2>z:
        foo=sm*(sm+1)
        foo//=2
        maxi-=foo
        foo=z+1-m1
        maxi-=(sm+1)*foo
        sol+=maxi
    if m2<=z and mx>z:
        foo=mx-z
        sol+=(foo*(foo+1))//2
    z+=1
print(sol)

A, B, C, D = [int(i) for i in input().split()]

count_ymz = [None for i in range(D-B + 1)]
for i in range(len(count_ymz)):
	count_ymz[i] = min(C, D-i) - max(C-i, B) + 1

pre_count_ymz = [None for i in range(len(count_ymz))]
pre_count_ymz[0] = count_ymz[0]
for i in range(1, len(count_ymz)):
	pre_count_ymz[i] = pre_count_ymz[i-1] + count_ymz[i]
ans = 0
for x in range(A, B+1):
	if x > D-B + 1:
		ans += pre_count_ymz[-1]
	else:
		ans += pre_count_ymz[x-1]

print(ans)