How to turn on the TV?

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Winter is coming. And Zenik and Marichka have bought a house and are settling into it.

It turns out the previous owners of the house thought that installing a large number of switches in a row would help save electricity, but that is not the case. However, Zenik and Marichka now have to live with it.

To turn on some appliance, you have to go through a whole quest. For example, \(n\) switches connected one after another are responsible for turning off the TV.

Each of the switches has the shape of a square and can be in one of two states:

• current can flow from the top-left corner to the bottom-right corner (we denote this state as \),

• current can flow from the bottom-left corner to the top-right corner (we denote this state as /).

All switches are located horizontally in a single row. For each pair of adjacent switches, the top-right and bottom-right corners of the left switch have electrical connections to the top-left and bottom-left corners of the right switch, respectively. See the illustration for the example in the Notes section for a better understanding.

Also, current is supplied to both inputs of the first switch, and both outputs of the last switch are connected to the TV.

Zenik knows the current state of all the switches. What is the minimum number of switches that need to be toggled so that the electrical current reaches the TV and it can be turned on?

Input

The first line contains a single integer \(n\) — the number of switches.

The second line contains a string \(s\) of length \(n\) which describes the states of all switches. If \(s_i =\) \, then the \(i\)-th switch is currently in the first state, and if \(s_i =\) /, then it is in the second.

Output

Output a single integer — the minimum number of switches that need to be toggled to turn on the TV.

Constraints

\(2 \le n \le 10^5\),

\(s\) consists exclusively of / and \ characters.

The task scoring consists of the following blocks:

• 1 point — the first example from the problem statement,

• 1 point — the second example from the problem statement,

• 13 points — a block of tests in which \(1 \le n \le 10\),

• 40 points — a block of tests in which \(11 \le n \le 1000\),

• 45 points — a block of tests in which \(1001 \le n \le 10^5\).

You will receive points for a block only if you give the correct answer to all tests in the block.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 /\///	1

Input (stdin) сopy	Output (stdout) сopy
3 //\	1

Notes

As can be seen from the figure — current flows from the first switch to the second, and from the second to the third. The position of the fourth switch does not allow the current to flow further.

But if you toggle only the fourth switch, the current will flow from the third to the fourth, from the fourth to the fifth, and from the fifth to the TV.