O(log n) algorithm

[_uj]

this is the entire spec.

The key is in the id numbers, like

99, 1, 2, 2, 1, 1, 1,

If they're all greater than 0 then the array elements will always form three sections in the array,

[losers][winners][losers]

In your example it becomes,

[-1, 0, 2] [4, 5, 6] []

(Any section can be empty)

In the first loser section the elements are smaller than the indexes, in the winner section they're equal, and finally in the last loser section they're larger.

The algoritm now must find the two borders between the winner section and the loser sections. And that can be done in O(log N). It's two binary searches finding the upper and lower border respectively.

Again note that the formation of three sections depends on all id numbers being greater than 0.

Examples,

1. {-1,0,1,2,4,5,6,7}

[-1,0,1,2,4,5,6,7] [] []

2. {-1,2,3,8,11,15}

[-1,2] [3] [8,11,15]