Problem Description

With the sound of waves by the sea and the music of the woods, there is a peaceful small town surrounded by mountains and water. People here rarely worry about their household items breaking down, because Kanan can always fix them. Kanan is the best mechanic in the area. Although she is still young, her skill and generous personality mean she often receives repair requests. It is said that even the isolated Demon King has to ask her for help when problems arise. During repairs, Kanan encounters all kinds of manuals. Some manuals have unbelievable folding structures. To understand the machine, Kanan unfolds the manual before repairing it, but after fixing it, folding it back along the original creases is even harder than the repair itself.

For any manual whose creases are all parallel to each other, we can number the creases $1, 2, \cdots, N$ from top to bottom according to the reading order of the text on the manual. These $N$ creases split the manual into $(N+1)$ paper strips. Each crease can be in one of two forms: one bulges inward perpendicular to the paper surface, corresponding to folding the upper and lower halves forward; the other bulges outward perpendicular to the paper surface, corresponding to folding the upper and lower halves backward. According to the shape of the crease cross-section, we use the lowercase letter v to represent an inward-bulging crease, and ^ (ASCII code $94$) to represent an outward-bulging crease. Assume all paper strips have the same width, and the manual does not deform during folding. Then after folding along a crease, the paper on both sides can coincide if and only if the creases on the two sides are opposite. That is, if we fold along the $k$-th crease, then for every positive integer $m$ such that $1\le k-m<k+m\le N$, the $(k-m)$-th crease and the $(k+m)$-th crease have opposite forms. For example, for a manual with creases v^v^^^^v in order, we can fold along its $7$-th crease. By definition, a manual can always be folded along the first or the last crease. After folding, the manual can be represented by the creases on the side of the folded crease that has more remaining creases. For instance, folding v^v^^^^v along the $7$-th crease yields v^v^^^. If the numbers of creases on both sides are equal, either side can be used to represent the folded paper, because the crease structure is rotationally symmetric in 3D space. In particular, for a manual with only one remaining crease, i.e. v or ^, after folding, all $(N+1)$ paper strips overlap. At this time, the manual is said to be folded neatly.

Although folding each crease one by one in order can always fold the manual neatly, Kanan thinks this is not aesthetically pleasing. An aesthetically pleasing folding method should use as few folds as possible, and each fold should make the two sides as symmetric as possible. Define the asymmetry degree of a folding method as the sum, over all folds, of the difference between the numbers of creases on the two sides of the folded crease. Given the creases of a manual, Kanan wants to know the minimum number of folds needed to fold the manual neatly, and among all folding methods with the minimum number of folds, the minimum possible asymmetry degree.

Input Format

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$, which represents 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: the minimum number of folds, and the minimum asymmetry degree under the condition that the number of folds is minimized. The two numbers should be separated by one space.

3
^vv

2 0

8
v^v^^^^v

6 15

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

14 201

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

24 663

Hint

Explanation of Sample #1

If you first fold in half along the middle crease, the paper on both sides coincides exactly. Then folding once more will fold the manual neatly.

Subtasks

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

Problem License

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

In the following, “this repository” refers to the THUPC2024 Preliminary official repository (https://github.com/ckw20/thupc2024_pre_public).

1. Any organization or individual may use or repost the problems in this repository for free.

2. When using the problems in this repository, any organization or individual should do so free of charge and publicly. It is strictly forbidden to use these problems for profit or to add special access restrictions to them.

3. If possible, when using the problems in this repository, please also provide ways to obtain resources such as the testdata, reference solution, and editorial. Otherwise, please attach the GitHub link of this repository.

Translated by ChatGPT 5