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"