P9964 [THUPC 2024 Preliminary] Multi-fold Difference Verification.

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

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 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.

### 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](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