I just leave the test generator here: [Codeforces] [Ideone] [Pastebin]

UPD. The similar blog entry about Java 6: http://codeforces.net/blog/entry/2296 (it's only in Russian, but you can look over source code)

UPD 2. 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.