Министр финансов Дормидонт был огорчён. Во-первых, царь Пантелеймон узнал, что в стране экономический кризис. Во-вторых, кабинету министров велено этот кризис устранить до праздника ватрушкопечения, а праздник-то, можно сказать, на носу.

И самое обидное — узнал-то Пантелеймон об этом по чистой случайности. Из-за прорыва на теплотрассе министр безопасности принял решение, что прогулка царя будет проходить по запасному маршруту. А этот запасной маршрут проходит мимо пункта обмена валюты. В прошлый раз Дормидонту удалось убедить Пантелеймона, что на табло отображается температура воздуха, но то было летом, да и числа были в два раза меньше.

Размышления привели Дормидонта к выводу, что для начала надо бы перенести праздник ватрушкопечения. Этой идеей он поделился с министром времяисчисления Харитоном, и теперь они обдумывают, как это сделать.

Год в царстве состоит из n дней. Некоторые праздники связаны с фиксированным номером дня, остальные же назначаются министром времяисчисления. Однако для каждого назначаемого праздника известно, после какого праздника он состоится.

Праздник ватрушкопечения назначаемый, и Харитон не против назначить его как можно позже. Однако при это нужно соблюсти следующие условия:

• во-первых, все запланированные в году праздники должны состояться;
• во-вторых, никакие два праздника не должны состояться в один день;
• в-третьих, все назначаемые праздники должны состояться после тех праздников, которые указаны как их предшественники.

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