Группа ДТП планирует беспрецедентное турне по Древляндии. Фанаты ДТП предвкушают событие и делают ставки, как много концертов даст любимая группа.

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

Достоверно известно, что музыканты проедут по некоторому пути, давая концерты в некоторых городах вдоль этого пути. Путь музыкантов не будет проходить по одному городу дважды, каждый раз они будут переезжать в ранее не посещенный город. Таким образом музыканты проедут по некоторому пути (не посещая никакой город дважды) и в каких-то (необязательно всех) городах вдоль пути дадут концерты.

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

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

Фанаты Древляндии судорожно пытаются понять, сколько концертов даст «ДТП» в Древляндии. Кажется, без помощи настоящего программиста не обойтись! Помогите фанатам найти искомое количество концертов.