시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 2 2 66.667%

문제

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

서브태스크

번호 배점 제한
1 42

$1 \le |s| \le 1000$

2 37

$1 \le |s| \le 200\,000$

3 21

$1 \le |s| \le 3\,000\,000$

예제 입력 1

ACGACA

예제 출력 1

3

예제 입력 2

AATTAA

예제 출력 2

2

힌트

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"

채점 및 기타 정보

  • 예제는 채점하지 않는다.