Morgan Stanley Interview Question

write a program which will find element such that a[i] = i with less than O(n) complexity.