SciComLove (2023)

Interview

Time limit2sMemory limit1024 MB

Summary

Given the prefix of length N of the repeated string SciComLove, flip the case of one character per query and print the uppercase count after each query.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

The math rabbit's favorite string is "SciComLove" (without the quotes). The rabbit loves it so much that it extended the string to length $N$ . The string becomes the prefix of length $N$ of the infinitely repeated "SciComLove". For example, if $N=15$ , the string is "SciComLoveSciCo".

The rabbit plays with this string over $Q$ rounds. The $i$ -th round goes as follows.

Flip the $X_i$ -th character of the string: an uppercase letter becomes lowercase, and a lowercase letter becomes uppercase. (Here $1 \le X_i \le N$ )

After each of the $Q$ rounds, write a program that prints the number of uppercase letters in the string. All changes accumulate.

Input

The first line contains two integers $N$ and $Q$ , separated by a space. From the second line through line $Q+1$ , each of the $Q$ lines contains one integer $X_1$ , $X_2$ , $\cdots$ , $X_Q$ .

Output

After each of the $Q$ rounds, print the number of uppercase letters in the current string on its own line.

Constraints

$1 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$
$1 \le X_i \le N$ ( $1 \le i \le Q$ )

Examples2

Example 1
Input
```
10 1
1
```
Expected output
```
2
```
Example 2
Input
```
10 3
1
2
3
```
Expected output
```
2
3
4
```