P16936 The Meaning of Time.

:::info[Problem Background] The air still carried the mixed smell of damp stone walls and rotten paper, as if that brilliant moment spanning a thousand years had only been a brief, almost luxurious dream. Yet the “Book of Time” truly lay in Frieren’s arms, its cover cold and quiet, like a fragment peeled from the past itself, calmly proving that everything that had just happened was not an illusion. Fern was the first to lower her head and look at the book, her voice so light it was as if she was afraid of disturbing something. “If we really can reverse time…” She paused. “I want to see Lord Heiter one more time.” When she said this, her expression was still calm, but the faint ripple deep in her eyes could not be completely hidden. The words she never got to finish, the memories that had clearly passed yet always resurfaced at some careless moment—those were not things she could easily put down with a single “it’s already over.” “Me too.” Stark scratched his head. For once he did not immediately show that usual slightly dull expression. “If we could go back, I really want to eat ice cream with my master one more time.” After saying that, he gave an embarrassed smile, but it only stayed for a very short moment. Sometimes the more ordinary a memory is, the more it makes people feel it is so far away that it cannot be touched. Frieren listened quietly and did not speak at once. She just lowered her head and looked at the “Book of Time” in her hands, her fingertips resting lightly on the ancient patterns on the cover. After a while, as if following a line of thought she had walked for many years, she softly said: “I probably would want to go back to the time when I fought together with Himmel and the others.” Fern raised her head and looked at her. “Not for fighting, and not to change anything.” Frieren’s voice was still calm, even so light it almost blended into the air. “It would be enough just to say a few more words to those old friends.” The hall fell silent. It was a short silence, yet it felt like it gently stirred many feelings that should have been sealed away. But right at this moment, the air around them suddenly felt wrong. At first, it was only a very slight vibration. Like muffled thunder from far away, or like something heavy rolling over the ground from a great distance. Then the remaining magic power deep in the library began to churn; the formerly stable spell patterns dimmed one after another, and even the stone floor under their feet seemed to sway slightly. Stark was the first to become alert and immediately gripped his weapon; Fern also raised her staff and quickly swept her gaze across the surroundings. “What’s going on?” she asked in a low voice. Frieren did not answer. Because before she could speak, the light outside the hall had already changed completely. The three quickly crossed the corridor and came to the edge of the high platform outside the “Sinking Star Archive.” But the scene before their eyes made all of them stop. The outside world was completely different. The forest that should have stretched in rolling waves had been replaced by大片焦黑与荒芜, and ominous gray smoke rose between distant mountain ranges. Wind blew in from the plains, carrying burned ash and the smell of blood, making it hard to keep one’s eyes open. Even farther away, traces of what used to be human settlements were left only as broken city walls, collapsed towers, and one empty ruin after another. The sky was not dark, yet the whole world seemed covered by a shadow that could not be driven away; even the sunlight looked pale and tired. “…How could this be?” Stark froze. Fern also could not speak for a moment. The world she knew—humans struggled, but still moved forward slowly; magic was not something everyone could master, yet it definitely had not disappeared; the Demon King had been defeated long ago, and the remaining monsters were only shadows not fully cleaned up after a long peace—that world now seemed to have been completely overturned, vanishing without a trace. In its place was an era where monsters still raged everywhere, and humans could only barely survive. “No.” Fern’s voice tightened slightly. “This is not our original world at all.” Frieren looked at the distant land swallowed by gray smoke and wilderness, and her gaze slowly sank. “Maybe,” she said slowly, “we changed the timeline.” As soon as those words were spoken, it felt as if everything around them became even quieter. Frieren lowered her eyes, glanced at the “Book of Time” in her arms, as if she had finally connected all those scattered oddities from just now. “A thousand years ago, humans’ understanding of magic was actually very limited,” she said softly. “The reason they could later quickly master many powerful ancient spell techniques was probably not only because their research itself made a breakthrough.” “And it was because…” Fern seemed to realize something, her breathing pausing slightly. “Because of the ‘Book of Time’.” Frieren continued her sentence. Her voice was still calm, but it made one’s heart turn cold little by little. “This book allows people to reach spell techniques and knowledge from other timelines. That is why mages in human society became stronger and stronger, and why the kingdom’s magic system could prosper so quickly, eventually gaining an advantage over monsters and the Demon King’s army step by step.” She paused, then raised her head and looked at this world that had become unrecognizable. “But now, we took this book away.” Fern fell silent. Stark finally understood what that meant, too. Without the “Book of Time,” humans in this world could no longer touch the magic that did not originally belong to this timeline. Fewer and fewer people studied magic, and truly powerful mages became harder and harder to appear. As a result, human civilization, which should have gradually grown stronger in history, was instead suppressed again by monsters, and the Demon King was never defeated. Magic did not become the force that pushed civilization forward; instead, it became a luxurious way of fighting that only a very small number of people could afford, and only a very small number of people were qualified to master. “So… all of this is because we took that book.” Fern said softly. Frieren did not answer right away. At this moment, a sharp and ear-piercing scraping sound suddenly came from the ruins below the archive. All three looked down at the same time. They saw a monster covered in dark armor slowly crawling out from behind a broken stone wall. It was not especially huge, but its body surface was densely carved with glowing runes. Those patterns kept changing and reorganizing as if alive, connecting with each other into a strange arrangement that made people dizzy. Its pupils glowed with a cold green light, and it let out a low hiss. It had clearly noticed the three above. “Again…” Stark frowned and immediately held his weapon in front of him. But Frieren’s expression changed slightly after just one glance. “It’s a rune monster,” she said in a low voice. “This kind of thing can’t be solved with brute force alone.” “What do you mean?” Stark asked. “The runes on its body are its core spell technique.” Frieren looked at the constantly changing glowing patterns, her gaze calm and quick. “Only when a specific rune arrangement is broken and disrupted, or解除 in the correct order, will it truly lose its defense. Otherwise, no matter how many attacks it takes, it can keep recovering by reorganizing the runes.” Fern stared at the monster below that was drawing closer, and her expression gradually grew serious. “Humans nowadays… can’t even handle a monster like this?” she asked softly. “Looks like the situation is not good,” Frieren replied calmly.

The rune monster has $n$ runes on its body, which can be approximated as a string $s$. Here $n$ is even, and the string contains only lowercase letters. Each time you cast a spell, you may perform the following transformations on the runes on the monster: - Remove runes $s_i$ and $s_j$ if and only if $s_i = s_j$ and $i\neq j$. - Replace rune $s_i$ with any lowercase letter $t$. The required magic cost is $|\text{ord}(s_i) - \text{ord}(t)|$. To kill the rune monster, you must delete all runes, making the string empty. Frieren does not want to spend too much magic power, and she wants to know what the minimum magic cost is.

The first line contains an integer $n (1\leq n\leq 10^5)$, representing the number of runes. The second line contains a string $s$ of length $n$. It is guaranteed that $s$ contains only lowercase letters.

Output the minimum magic cost to turn $s$ into an empty string.

The $\text{ord}(·)$ function is the ordinal function, and its return value is the index of the character in ASCII code; for example, $\text{ord}(a)=97, \text{ord}(c)=99$. :::info[Problem Background] --- The monster, having lost the support of its runes, gradually crumbled into dust. The glowing patterns went out, and the remains were quickly buried by wind and sand. But none of the three looked relaxed. Gray smoke still rose in the distance; claw marks and scorch blackness left by monsters still remained among the ruins; even the land under their feet seemed to silently tell the same thing—this world had been rewritten far too much. Frieren lowered her head and looked at the “Book of Time” in her arms, not speaking for a long time. The book was still quiet, as if all changes had nothing to do with it, but it was exactly this silence that made it feel heavier than any monster. Fern also stared at the book, her fingers tightening slightly. As long as it was still there, the wishes in her heart—wishes she almost did not dare to think about—were not completely impossible. To see Heiter again, to hear that gentle yet slightly helpless voice one more time, to be calmly looked at by him like before—those were not things she could easily give up. Stark did not speak. He just stood to the side, looking at the barren plain, then at Fern and Frieren, as if he also understood that this decision should not be made by someone else for her. Wind passed through the broken high walls, sweeping up fine ash. Fern was silent for a long time, so long that even breathing seemed to be drawn out. Of course she knew that the human heart longs for miracles. If she were just a little more selfish, if she pretended not to see the ruins and suffering along the way, if she told herself “there will always be another way,” then the book could still remain in their hands. Besides, even if this world had become cruel to this extent, with her status and power as a first-class mage, she could still find her own place. But it should not be like this. She thought of those empty villages, of the white bones in the wilderness that no one collected, of humans who looked so powerless even against a single rune monster. She wanted to see Heiter, but she did not want to trade the pain of countless people for this one reunion. She missed the past, but she did not want the entire world to be stuck forever on a timeline that could not move toward the future. So Fern finally raised her head slightly. Her voice was not loud, but it was unusually clear. “We need to return the ‘Book of Time’.” When she said this, she almost did not hesitate anymore. It was as if something that had been wavering finally settled back into the position it should have in her heart. It was not because she had no regrets, and not because she no longer missed Heiter. It was precisely because that longing was so real that she understood even more clearly that she could not, for a personal wish, watch more people continue to suffer in this wrong world. Frieren quietly looked at her for a while. Then she gave a very light smile. The smile was faint, yet more gentle and more certain than any comfort along the way. “That’s my disciple,” she said. Translated by ChatGPT 5