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

Каждая доминошка представляет собой пару чисел a, b — количество точек на двух половинах доминошки. Цепочкой называется последовательность доминошек, которую можно выложить в линию так, что для любых двух соседних доминошек с номерами i, i + 1 в этой линии верно следующее: b_i = a_i+1. Доминошки нельзя поворачивать и переворачивать.

Формат входных данных

В первой строке дано число n (1 ≤ n ≤ 100000) — количество доминошек. В следующих n строках даны пары чисел a_i, b_i (0 ≤ b_i ≤ a_i ≤ 10⁹) — описание доминошек.

Формат выходных данных

В единственной строке выведите одно число — максимальную длину цепочки из доминошек.

Пример