Question
Count Number of Valid Triangles
You are given the lengths of n sticks. Your task is to count the number of distinct triplets of sticks that can form a triangle. A triplet (a, b, c) can form a triangle if and only if the triangle inequality holds: a + b > c, a + c > b, and b + c > a.
Input
The first line contains an integer n, representing the number of sticks.
The second line contains n integers, where the i-th integer represents the length of the i-th stick.
The second line contains n integers, where the i-th integer represents the length of the i-th stick.
Output
Print a single integer — the number of distinct triplets of sticks that can form a triangle.
Example
Input
4
4 6 3 7
Output
3
Explanation
The valid triangles are formed by the triplets:
(3, 4, 6), (4, 6, 7), and (3, 6, 7).
Each satisfies the triangle inequality conditions.
Input
5
1 1 1 3 5
Output
1
Explanation
Only one valid triangle can be formed: (1, 1, 1).
All other triplets fail the triangle inequality.
4
4 6 3 7
Output
3
Explanation
The valid triangles are formed by the triplets:
(3, 4, 6), (4, 6, 7), and (3, 6, 7).
Each satisfies the triangle inequality conditions.
Input
5
1 1 1 3 5
Output
1
Explanation
Only one valid triangle can be formed: (1, 1, 1).
All other triplets fail the triangle inequality.