Sasha and Vasya began to engage in tap dancing. The dance consists of stomps with feet on the floor. But as they learn very quickly, they decided to experiment with choreography.

The choreography of tap dance is described with a sequence of two letters L and R. L means stomping with left foot, and R means stomping with right foot correspondingly. Sasha realized that the best part of this dance is the one that does not use the same foot in succession. He identified the importance of choreography as the largest contiguous sequence with no two consecutive characters.

As you know, the creation of a beautiful dance is a very complicated process, with many small changes before the best option is found. Therefore, Bob wants to know the value of the choreography after each change. The change is a replacing of L to R (or vice versa) at some position.

Before all changes the sequence consists of letters L only.

Input

The first line contains two integers: the length of choreography n (1 ≤ n ≤ 200000) and number of changes q (1 ≤ q ≤ 200000). Each of the next q lines contains one number giving the replacing position.

Output

Print q integers, one per line: the value of choreography after each change.