We have an array of integer and we want at evey odd index i we have to find sum of first i/2 smallest number from index 1 to index i

lets

At index 1 sum of 0 smallest number

At index 3 sum of first one smallest number

At index 5 sum of first two smallest number

At index 7 sum of first three smallest number

At index 9 sum of first four smallest number

and so on.

any solution/Idea in o(n) or o(nLogn) ?