Problem D
Python Commenting

Commenting out some Python code in VS Code.

There exists an IDE and text editor named Visual Studio Code (which you might be using right now). When using it to edit a file, if you select the lines of text in the closed interval $[L, R]$ and press Ctrl+/, one of the following two things happens:

1. If at least one of the lines selected has not been commented out already, then each of the lines from $L$ through $R$ add one comment indent, represented by a new “# ” prefixing each of those lines.

2. If all of the lines selected have been commented out at least once, then each of the lines from $L$ through $R$ remove one comment indent, represented by the “# ” at the beginning of those lines being removed.

For example, with the following code:

1 sum = 0

2 for i in range(10):

3 sum += i

4 print(sum)

If you were to select lines $2$ through $4$ and comment them out, then you would have:

1 sum = 0

2 # for i in range(10):

3 # sum += i

4 # print(sum)

After another operation with $[L, R] = [1, 3]$:

1 # sum = 0

2 # # for i in range(10):

3 # # sum += i

4 # print(sum)

And then with one more operation with $[L, R] = [3, 4]$:

1 # sum = 0

2 # # for i in range(10):

3 # sum += i

4 print(sum)

You are given some code with a valid sequence of operations of type 1 having been applied but none of type 2 having been applied. Calculate the minimum number of commenting operations needed to produce the given code, assuming the code originally started out with no comments.

Input

The first line of input gives $n$ ($1 \leq n \leq 10^4$), the number of lines of code present. The next $n$ lines all have some code on them (literally), with some (possibly no) instances of “# ” at the beginning of them.

Output

Print out the minimum number of commenting operations needed to produce the given code.

3
some code
some code
some code

0

4
# some code
# # some code
# # some code
# some code

2

13
some code
# some code
# some code
# # # some code
# # # some code
# # some code
# # some code
# # some code
# some code
some code
# some code
# # some code
# some code

5