We want to construct a tetrahedron (a triangular pyramid) in such a way that one of its vertices coincides with the origin of the 3D frame, and each one of the other three vertices belongs to one of the three axes of the 3D frame.
Formally, let A, B, C, D be the 4 vertices of the tetrahedron, then : \(A = (0,0,0)\), \(B = (X,0,0)\), \(C = (0,Y,0)\) and \(D = (0,0,Z)\), where \(X\), \(Y\) and \(Z\) are positive integer numbers. When \(X\) divides \(Y\) and \(Y\) divides \(Z\) the tetrahedron is called beautiful.
You have an array A of integer numbers, you can chose any three elements \(A_i, A_j, A_k\), \(i < j < k \) as dimensions of the tetrahedron (values of \(X,Y,Z\) Respectively).
How many beautiful tetrahedrons you can construct ?
Input starts with a line containing one integer \(N\) (\(1 \leq N \leq 1500\)) Then follows \(N\) integers denoting the array \(A\) (\( 1 \leq A_i \leq 10^9\)).
Output one integer : the number of beautiful tetrahedrons.
- \(N \leq 100\) (\(30\) Points).
- \(N \leq 1500\) (\(70\) Points).
5 1 2 3 4 5