問題一覧 > 通常問題

No.2454 Former < Latter

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 84
作問者 : srjywrdnprkt / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9858 / 自分の提出
問題文最終更新日: 2023-08-21 08:05:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 403 (順位表) の他の問題:

Problem Statement

You are given a string $S=S_1S_2\cdots S_N$ of length $N$ consisting only of lowercase English letters.

Among the integers $i$ satisfying $1\leq i\leq N-1$, find the total number of those for which, letting $U=S_1\cdots S_i$ be the first part and $V=S_{i+1}\cdots S_N$ be the second part of the strings obtained by splitting $S$ at the $i$-th character, $U$ is strictly smaller than $V$ in lexicographical order.

You are given $T$ test cases; find the answer for each of them.

Input

$T$
$case_1$
$\vdots$
$case_T$
Here, $case_i$ is the $i$-th test case. Each test case is given in the following format.
$N$
$S$

The input satisfies the following constraints.

  • $T, N$ are integers
  • $1\leq T$
  • $2\leq N$
  • $S$ is a string of length $N$ consisting only of lowercase English letters
  • For the test cases contained in $1$ input, the sum of their $N$ does not exceed $3\times 10^5$.

Output

Output $T$ lines. On the $i$-th line, output the answer to the $i$-th test case.

Sample

Sample 1
Input
3
6
banana
26
abcdefghijklmnopqrstuvwxyz
7
xxxxxxx
Output
2
25
3

For test case number $1$,

  • When $i=1$, $U=b, V=anana$ and $U > V$.
  • When $i=2$, $U=ba, V=nana$ and $U < V$.
  • When $i=3$, $U=ban, V=ana$ and $U > V$.
  • When $i=4$, $U=bana, V=na$ and $U < V$.
  • When $i=5$, $U=banan, V=a$ and $U > V$.
Therefore, the number of $i$ satisfying the condition is $2$, namely $i=2, 4$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。