Given a sequence of numbers A[1…N], find the number of pairs of i, j (i < j), such that A[i] * A[j] > A[i] + A[j].
This problem is similar to this one occurred in OCT Long 2013. It is easy to find that if both A[i] and A[j] are greater than or equal to 2, the inequality A[i] * A[j] > A[i] + A[j] always holds. It is worth noting that, if any one of A[i] and A[j] is 0 or 1, the inequality will never hold. It is also not held for both numbers are 2.
Denote C2 as the number of 2s in the given array. And C is the number of numbers which are greater than 2.
As analyzed before, the answer is C2 * C + C * (C - 1) / 2.