I was recently solving a problem on Hacker-Earth and there was a particular subtask I needed to complete to submit the solution successfully. Say, I am given an array of integers.pick a pair (i,j) such that 'i' is less than 'j'. The task was to find out the number of times this pair will occur in all the contiguous subarrays of the given array.

for example : number of elements — n = 5; given array — 1 2 3 4 5

subarrays of given array — (1,2) (2,3) (3,4) (4,5) (1,2,3) (2,3,4) (3,4,5) (1,2,3,4) (2,3,4,5) (1,2,3,4,5)

pair (1,2) occurs 4 number of times in subarrays (1,2) , (1,2,3) , (1,2,3,4) and (1,2,3,4,5); similirialy, pair (3,4) occurs 6 number of times in subarrays (3,4) , (2,3,4) , (3,4,5) , (1,2,3,4) , (2,3,4,5) , (1,2,3,4,5);

Now, I found that for every pair (i,j) such that i<j, can find it ** (n-j+1)*i ** number of times. Can anybody please explain with mathematical proof, why this particular expression is working?

Thank you.