put
n
at the left end of that permutation
ptr[n]->link = p->link;
p->link = ptr[n];
pred[n] = p;