Китнисс находится в очень длинном прямом тоннеле и хочет из него выбраться. Она может передвигаться вдоль тоннеля в обоих направлениях. В тоннеле есть ровно один люк, если добраться до которого, через него будет можно выйти из тоннеля.

К сожалению, не всё так просто. В некоторых $n$ местах располагаются решётки во всю ширину тоннеля, через которые невозможно пройти. Решётки заперты на замки, и, пока Китнисс не отопрёт замок, она не сможет преодолеть соответствующую решётку. Также в некоторых $n$ точках вдоль тоннеля располагаются $n$ ключей. Каждый из $n$ замков можно отпереть ровно одним из этих $n$ ключей. После того, как замок вскрыт, Китнисс может свободно и сколько угодно раз проходить через решётку, которая запиралась этим замком. Китнисс может подбирать и носить с собой неограниченное число ключей.

Китнисс известно расположение люка, всех $n$ решёток с замками, всех $n$ ключей, ей известно, какой ключ какой замок отпирает, и, разумеется, ей известно, где находится она сама. Определите, преодолев какое наименьшее расстояние, Китнисс сможет выбраться из тоннеля.