21896번 - Life in Innopolis 서브태스크다국어

문제

$$\mathbb{INNOPOLIS} ~ \mathbb{TIMES}$$

December, 18, 2016

Is there life in Innopolis?

Life in Innopolis could have been brought by space body. That's a conclusion made by a scientist after examining the consistency of water taken from this area: strange DNA structure interested him. Research would take years...

To speed up the process of research, he turned to you. Let's represent DNA as a string $s,ドル consisting of four uppercase letters, one for each nucleotide: "A", "C", "G" and "T". Scientist has only one question: for how many positions $i$ suffix starting at position $i$ is lexicographically less than suffix starting at position $i + 1$.

Suffix is a sequence of consecutive characters, ending with the last character of the string. String itself is also its suffix. For example, ACGC, CGC, GC, and C are all suffixes of string ACGC.

String $a$ is lexicographically less than string $b,ドル if there is such $k$ that first $k$ characters of $a$ and $b$ coincide and $a_{k+1} < b_{k+1},ドル or if $a$ is shorter than $b$ and $a_i = b_i$ for all $i \le |a|$. For example, "A" < "G", "AAG" < "AAT", "AGC" < "AGCA".

입력

Input contains a single string $s,ドル consisting of uppercase letters of Latin alphabet: "A", "C", "G" and "T".

String length doesn't exceed 3ドル,000円,000円$.

출력

Output a single integer --- number of positions $i$ such that suffix starting at $i$ is lexicographically less than suffix starting at position $i + 1$.

제한

서브태스크

힌트

There are three such positions in the first example:

1. $i=1$: "ACGACA" < "CGACA"
2. $i=2$: "CGACA" < "GACA"
3. $i=4$: "ACA" < "CA"

And only two positions in the second one:

1. $i=1$: "AATTAA" < "ATTAA"
2. $i=2$: "ATTAA" < "TTAA"