有一种抽签的方法，是有很多根竖线，然后竖线的中间有若干条横线连接。最下面有一个目标的点。

你要选择某一根竖线，从上到下，一旦遇到一根横线，就移动到它连接的另一根竖线上。保证同一高度不会有两个横线连接，一定只会连向左边或者右边中的一个，或者没有。

请你求出，从哪一根竖线开始可以走到目标位置。竖线从左到右编号 $1$ 到 $n$。

输入格式见样例。