Here is an algorithmic problem. Consider read-write array A[1,n] of numbers. Find the smallest index i such that A[i]=A[j] for some j, that is the smallest index that has a duplicate in the array, using O(1) extra space only. We work in the compare and move model typically used for sorting, and are not allowed to "stuff bits" into array items. This problem was given to me by Martin Pal and Vitaliy Kulikov of Google. Results we can claim are: O(nlog^2 n) time without destroying the array, and O(nlog n) time if one is allowed to destroy the array. Any thoughts/pointers welcome. The problem has nice connections to in-place mergesort, for example.