Listening to the tides by the sea, hearing the sounds of nature in the forest. This is a quiet and peaceful town by the mountains and water, where people rarely worry about their household items breaking, because Kanan can always fix them. Kanan is the premier mechanic in this region; although she is young, her skilled techniques and generous personality mean she is always receiving repair requests, and it is said that even the reclusive Demon King has to seek her help when encountering problems. When helping people with repairs, Kanan encounters all sorts of strange instruction manuals. Some of these manuals have incredible folding structures. To understand the construction of the machinery, Kanan unfolds the manuals before repairing them, but folding them back into their original state along the original creases after the repair is often more difficult than the repair itself.

For manuals where all creases are parallel, we can number each crease $1, 2, \cdots, N$ from top to bottom in the order they appear in the text. These $N$ creases divide the manual into $(N+1)$ strips of paper. Each crease can be one of two types: one that protrudes inward perpendicular to the paper, corresponding to folding the top and bottom halves of the paper forward; and one that protrudes outward perpendicular to the paper, corresponding to folding the top and bottom halves backward. Based on the shape of the crease cross-section, we use the lowercase letter v to represent an inward-protruding crease and ^ (ASCII code $94$) to represent an outward-protruding crease. Assuming all paper strips have the same width and the manual does not deform during the folding process, the paper on both sides of a crease can overlap after folding if and only if the creases on both sides are opposite; that is, if we fold along the $k$-th crease, then for all positive integers $m$ satisfying $1\le k-m < k+m\le N$, the $(k-m)$-th crease and the $(k+m)$-th crease must have opposite shapes. For example, for a manual with creases v^v^^^^v, one can fold along the $7$-th crease. By definition, a manual can always be folded along the first or last crease. After folding, the manual can be represented by the creases on the side with more remaining creases; for example, v^v^^^^v folded along the $7$-th crease results in v^v^^^. If the number of creases on both sides of the folded crease is equal, either side can be used to represent the folded paper, as the creases are rotationally symmetric in three-dimensional space. Specifically, after folding a manual with only one remaining crease, i.e., v or ^, all $(N+1)$ strips of paper overlap, and the manual is said to be folded neatly.

Although folding each crease in order will always result in a neatly folded manual, Kanan feels this is not aesthetically pleasing. An aesthetic folding method should involve as few folds as possible, and the creases on both sides should be as symmetric as possible during each fold. Define the asymmetry of a folding method as the sum of the differences in the number of creases on both sides of the folded crease for each fold. Given the creases of a manual, Kanan wants to know the minimum number of folds required to fold the manual neatly, and the minimum asymmetry among all folding methods that use the minimum number of folds.

Input

The first line contains a positive integer $N$, representing the number of creases. It is guaranteed that $1\le N\le 5000$.

The second line contains a string $s$, representing the creases in order. It is guaranteed that $|s|=N$ and $s$ consists only of v and ^.

Output

Output a single line containing two non-negative integers, representing the minimum number of folds and the minimum asymmetry under the condition of minimizing the number of folds, separated by a space.

Examples

Input 1

3
^vv

Output 1

2 0

Note 1

If you fold along the middle crease first, the paper on both sides will overlap perfectly, and then you can fold it neatly with one more fold.

Input 2

8
v^v^^^^v

Output 2

6 15

Input 3

40
v^vv^v^^v^^vvvv^v^^v^^^vv^^vvvv^v^^v^^^v

Output 3

14 201

Input 4

56
v^vvvvvvv^v^^vv^v^^v^^^^v^^v^vvvv^^vvvv^v^^v^^^vv^^vv^v^

Output 4

24 663

Subtasks

For all data, it is guaranteed that $1\le N\le 5000$, $|s|=N$, and $s$ consists only of v and ^.