In my solution I had to solve following interesting subproblem.

Given an array. There is somewhere a unique cutpoint in this array. We don't know where, but we can check, if x is a cutpoint in O(1). We have to find this cutpoint, split array in two parts and do the same recursively on both parts. We need to do it faster than in O(n^2).

Solution:
For a segment (l, r) check for cutpoints in following order: l, r, l+1, r-1, l+2, r-2, ...