Problem G
Neighborhood Watch

Jennifer was nominated to be neighborhood watch captain and is now in charge of managing the watch for her street.

Jennifer’s street consists of houses on only one side of the road. She has a plan of which houses will be a neighborhood watch house and wants to know how safe the plan is. A walk from one house to another house (not necessarily distinct) is considered safe if there is at least one house along the walk that is a neighborhood watch house. The safety rating of a plan is the number of walks that are safe on the street. Since a walk is either safe or not safe, when traveling in either direction, it is not counted twice in the safety rating.

\includegraphics[width=0.7\textwidth ]{houses}
Figure 1: Sample input. One example of a safe walk is traveling from house $1$ to house $5$.

Tell Jennifer the safety rating of her plan.


The first line of input contains two integers $N$ ($1 \leq N \leq 200\, 000$), which is the number of houses on the street, and $K$ ($0 \leq K \leq N$), which is the number of neighborhood watch houses in Jennifer’s plan. The houses are numbered $1, \dots , N$.

The next $K$ lines describe the neighborhood watch houses. Each of these lines contains a single integer $H$ ($1 \leq H \leq N$), which is the house number of a neighborhood watch house. The house numbers are given in strictly increasing order.


Display the safety rating of Jennifer’s plan.

Sample Input 1 Sample Output 1
5 2

Please log in to submit a solution to this problem

Log in