List of integers & L.I.S.

[n00m]

Given a list of N arbitrarily permutated integers from set {1..N}.
Need to find the ordering numbers of each integer in the LONGEST
increasing sequence to which this number belongs. Sample:

List:
[4, 5, 6, 1, 2, 7, 3]

Corresponding ordering numbers:
[1, 2, 3, 1, 2, 4, 3]

Details:
e.g. number 7 belongs to increasing sequence 1, 2, 7;
but this sequence is not the LONGEST sequence for "7".
The longest sequence for the 7 is 4, 5, 6, 7.
So, the 7's ordering number in this sequence is 4.

The salt of the thing is to do this with an O(n*log(n))
algorithm!
The straightforward O(n^2) algorithm is toooo slooow.

Any ideas?