Count Triangles

题意翻译

### 题目描述 给出四个整数$A,B,C,D$ ，其中$1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^5$ 求三边长分别为 $x,y,z$ 并且满足 $A \leq x \leq B \leq y \leq C \leq z \leq D$ 的非退化三角形（三顶点不共线）的个数 ### 输入格式 一行四个整数： $A,B,C,D$。 ### 输出格式 一行，输出满足条件的三角形个数。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

1 2 3 4

输出样例 #1

4

输入样例 #2

1 2 2 5

输出样例 #2

3

输入样例 #3

500000 500000 500000 500000

输出样例 #3

1

说明

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 $ .