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

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице \(М\). А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до \(N\) и собрали информацию о типе асфальта на каждом из участков — числа \(t_1, t_2, ... , t_N\) (\(t_i\) — номер типа асфальта на \(i\)-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна \(3\), потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную \(1\).

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

На протяжении многих лет Вася работает программистом в одной очень большой и очень известной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.

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

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от \(1\) до \(N\), где горная цепь с номером i представляет собой ломаную на плоскости из \(l_i\) звеньев с вершинами в точках (\(x_i\),\(j\) , \(y_i\),\(j\) ), причем для любых \(i\), \(j\) выполнено \(x_{i,j} < x_{i,j+1}\).

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа \(A\) и \(B\), что для любого номера \(i\) горной цепи выполнено \(x_{i,0} = A, x_{i,l_i} = B\).

Отметим, что из определения горной цепи следует, что для любого значения абсциссы \(A \le x \le B\) на ломаной с номером \(i\) существует единственная точка (\(x\), \(y_i\)(\(x\))) с этим значением абсциссы, принадлежащая этой ломаной. Будем говорить, что горная цепь \(i\) находится строго выше горной цепи \(j\) в точке \(x\), если выполнено строгое неравенство \(y_i(x) > y_j (x)\).

Естественно считать, что цепь под номером \(i\) пересекается с цепью под номером \(j\), если существуют такие два значения абсциссы \(x_1\), \(x_2\), что цепь \(i\) находится строго выше цепи \(j\) в точке \(x_1\), но при этом цепь \(j\) находится строго выше цепи \(i\) в точке \(x_2\), то есть выполнены неравенства \(y_i\)(\(x_1\)) > \(y_j\) (\(x_1\)) и \(y_j\) (\(x_2\)) > \(y_i\)(\(x_2\)). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.

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

Всего на урок пришло \(N\) детей, изначально построившихся таким образом, что рост стоящего на позиции \(i\) равен \(h_i\) (используется нумерация c \(1\)). Можно считать, что все числа \(h_i\) различны и лежат в диапазоне от 1 до \(N\). Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьников, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях \(i\) и \(j\), если \(h_i < h_j\) . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше преподаватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в шеренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всеволодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.