Problem Description

By the sea, one listens to the tides; in the forest, one hears the whispers. This is a peaceful town nestled between mountains and waters, where people rarely worry about their household items breaking down, as Kanan always fixes them for everyone. Kanan is the premier mechanic in this area; despite her youth, her skilled craftsmanship and generous nature mean she often receives repair requests. It is said that even the reclusive demon king has to seek her help when faced with problems. When helping people repair items, Kanan encounters all sorts of user manuals. Some of these manuals have incredible folding structures. To understand the mechanics, Kanan unfolds the manuals before repairs, but folding them back according to the original creases is more challenging than the repairs themselves.

For manuals with parallel creases, each crease can be numbered from top to bottom in the reading order as $1, 2, \cdots, N$, dividing the manual into $(N+1)$ strips. Each crease can be one of two forms: one that protrudes inward perpendicular to the paper, corresponding to folding the top and bottom halves forward; the other protrudes outward, corresponding to folding the top and bottom halves backward. These forms are represented by the lowercase letters v for inward protrusion and ^ (ASCII code $94$) for outward protrusion. Assuming all strips have the same width and the manual does not deform during folding, the sides can align along a crease if and only if the creases on both sides are opposite; that is, if folding along the $k$-th crease, then for all positive integers $m$ satisfying $1 \le k-m < k+m \le N$, the $(k-m)$-th and $(k+m)$-th creases are opposite. For example, for a manual with creases v^v^^^^v, it can be folded along its 7th crease. By definition, a manual can always be folded along either the first or the last crease. After folding, the manual can be represented by the side with more remaining creases, such as v^v^^^^v folded along the 7th crease resulting in v^v^^^. If both sides have an equal number of creases, either side can represent the folded manual, as the creases are rotationally symmetric in three-dimensional space. Specifically, folding a manual with only one crease, either v or ^, results in all $(N+1)$ strips overlapping, at which point the manual is considered neatly folded.

Although folding each crease in order will eventually neatly fold the manual, Kanan finds this unappealing. An appealing folding method should minimize the number of folds and ensure each fold is as symmetrical as possible. The asymmetry of a folding method is defined as the sum of the differences in the number of creases on both sides of each fold. Given the creases of a manual, Kanan wants to know the minimum number of folds required to neatly fold the manual, and among all methods with the minimum number of folds, the minimum asymmetry.

Input Format

The first line of input 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 each crease in order. It is guaranteed that $|s| = N$ and $s$ consists only of v and ^.

Output Format

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.

Sample Input and Output

Sample Input #1

3
^vv

Sample Output #1

2 0

Sample Input #2

8
v^v^^^^v

Sample Output #2

6 15

Sample Input #3

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

Sample Output #3

14 201

Sample Input #4

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

Sample Output #4

24 663

Notes

Sample #1 Explanation

If you fold along the middle crease first, the sides align perfectly, and then folding once more neatly folds the manual.

Subtasks

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

Usage Agreement

From THUPC2024 (2024 Tsinghua University Student Programming Contest and University Invitational) Preliminary.

The term "this repository" refers to the official THUPC2024 Preliminary repository (https://github.com/ckw20/thupc2024_pre_public).

1. Any organization or individual may freely use or repost the problems in this repository.
2. Any organization or individual using the problems in this repository must do so without charge and openly, and must not use these problems for profit or add special privileges to them.
3. If possible, please provide access to data, standard solutions, problem explanations, and other resources when using the problems from this repository; otherwise, please include the GitHub address of this repository.

见题面 Input 部分

见题面 Output 部分