Obligatory IDPC Problem

Limits: 1s, 512 MB

There are n people busy with arranging the upcoming Inter Department Programming Contest (IDPC) 2016.They call for the final meeting to finalize the contest rules. They select a room that is large enough to accommodate n people. Every person is wearing shoes of distinct color (each person has shoes of the same color on both feet but is different from another person). Before starting the meeting everyone took off their shoes outside the room. But suddenly load shedding occurs so that all of them end the meeting and begin leaving the room. In the dark, they are have trouble recognizing their shoes as all of them are of the same size. So every person picked two shoes at random and wore them without identifying which one is for the left feet and which one is for right. Now all of them are standing sequentially from 1 to n.

This is a companion discussion topic for the original entry at https://toph.co/p/obligatory-idpc-problem