Merchant's Shortest Travel Time

A merchant from the capital city (labeled as (1)) frequently travels to other towns for business. There are (N) towns in total. Among the towns labeled (2, 3, \ldots, N), every pair of towns is directly connected by a road, and traveling any such road takes unit time. There may also be direct roads between the capital and some other towns. It is guaranteed that starting from the capital, every town is reachable. The merchant starts from the capital and wants to visit every other town (each exactly once) by choosing an optimal route.

Determine the minimum travel time required.

Observation: Since all towns (except the capital) are fully connected, once the merchant leaves the capital via any direct road, he can visit the remaining towns in an order such that each move takes unit time. Therefore, if at least one direct road from the capital exists (which is ensured by the connectivity guarantee when (N > 1)), the minimum travel time will be (N - 1) (and (0) when (N = 1)).

inputFormat

The input consists of:\

• The first line contains a single integer (N) ((1 \leq N \leq 10^5)) representing the number of towns.\
• If (N > 1), the second line contains (N - 1) space-separated integers, where the (i)-th integer (for (i = 1, 2, \ldots, N-1)) is either 0 or 1. The (i)-th integer indicates whether there is a direct road between the capital (town 1) and town (i+1) (1 means there is a direct road, 0 means there is not). It is guaranteed that at least one of these integers is 1, ensuring that every town is reachable from the capital.

outputFormat

Output a single integer: the minimum travel time required for the merchant to visit every town starting from the capital.

sample

1

0