We retain position of each element of the order and then we verify for each edge p1-p2 if pos[p1] > pos[p2]...
We just need all edges so 100,000 * 2 * 2 (2 shorts for node id) = 400K