Birds on a Wire

On a single wire, there are \(N\) birds. Each bird faces either left (denoted by q) or right (denoted by p). Each bird can only see the bird immediately adjacent in the direction it is facing. Given the sequence of directions for the \(N\) birds, calculate the number of birds that are seen by 0 other birds, the number of birds seen by exactly 1 other bird, and the number of birds seen by exactly 2 other birds.

Example:

For \(N=6\) with the sequence: p q p p q q, the visibility is as follows:

• Bird 1 (p) sees bird 2.
• Bird 2 (q) sees bird 1.
• Bird 3 (p) sees bird 4.
• Bird 4 (p) sees bird 5.
• Bird 5 (q) sees bird 4.
• Bird 6 (q) sees bird 5.

The counts are:

• 2 birds (birds 3 and 6) are seen by 0 other birds.
• 2 birds (birds 1 and 2) are seen by exactly 1 other bird.
• 2 birds (birds 4 and 5) are seen by exactly 2 other birds.

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 10^5\)), the number of birds. The second line contains \(N\) characters separated by spaces. Each character is either p (facing right) or q (facing left).

outputFormat

Output three integers separated by a space: the number of birds seen by 0 birds, by 1 bird, and by 2 birds respectively.

sample

6
p q p p q q

2 2 2