UPD. The similar blog entry about Java 6: http://codeforces.com/blog/entry/2296 (it's only in Russian, but you can look over source code)
The link was updated. Generator's speed was increased a bit. However, it seems that something works wrong and for some array sizes it generates easy-to-sort array. Always check if sort really works slow.
UPD 3. Links were updated again. It works almost just as planned now. There is still one issue that I don't know how to fix, but in general it works and can be used.