Sorting models P68602

Masao is enjoying one of his wild parties with n models at home. At this moment, he is sitting on one of the n + 1 chairs of his flat. As expected, the rest of chairs have each a gorgeous model sitting on it. Masao stands up, thus leaving an empty chair, and uses his charisma to propose an innocent game to the models: to move around and change as fast as they can the chair they are sitting on. As a result, and after a while, Masao is watching how the models crash, fall to the ground, stand up, laugh, … such a remarkable spectacle!

But Masao’s powerful mathematical brain starts digressing: “Let’s suppose that I assign a label from 1 to n+1 to every chair, and a label from 1 to n to every model. If movements must be made one by one, and always to the current empty chair, how fast can the models sort themselves? Moreover, it would be nice if, at the end of the process, the only empty chair would be that with label 1 or that with label n+1.”

Can you solve Masao’s problem?

Input

Input consists of several cases. Every case begins with the number of models 1 ≤ n ≤ 10⁶ (yes, one million, Masao is improving himself). Follow the information of the n+1 chairs, from 1 to n+1. If the chair is the one left empty by Masao, we have his name. Otherwise, we have the model’s name and her label. Every case includes all labels from 1 to n.

Output

For every case, print the minimum number of movements of the models so that, at the end, they are arranged in increasing order by label, and the only empty chair is 1 or n+1.