Given an array A, for each element of the array find the number of elements in the array that are divisible by the element and also occur before it.
The first line contains a single integer N
The second line contains N integers representing the array A
1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^6
print N lines containing one integer
8 1 28 4 2 6 7
I hope the question is clear. simple approach is to run a loop for element to find the no. of elements divided by it. But it’s complexity is O(N^2) which will get TLE for sure. Can someone help me out in providing a better approach
PS : this problem is not from any ongoing contest , it was asked in my institution.