Generate Least Derangement
int D [ N + 1 ] ; for ( int i = 1 ; i <= N ; i ++ ) { int d = PQ . top ( ) ; PQ . pop ( ) ; if ( d != S [ i ] i == N ) { D [ i ] = d ; } else { D [ i ] = PQ . top ( ) ; PQ . pop ( ) ; PQ . push ( d ) ; } } if ( D [ N ] == S [ N ] ) swap ( D [ N - 1 ] , D [ N ] ) ;