E. Ксениа ба Тэмдэгт мөртэй бодлого

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Кодер Ксениа Информатикийн олимпиадад оролцохоор явж тэмдэгт мөртэй бодлого бодох ёстой болжээ. Гэсэн ч тэр энэ төрлийн бодлогуудад тийм ч сайнгүй. Түүнд тусална уу.

$s$ тэмдэгт мөр гэдэг нь $s_1s_2... s_{|s|}$ тэмдэгтүүдийн дараалал ба |s|-ээр үүний уртыг тэмдэглэдэг.

$s$-н дэд тэмдэгт мөр $s[i... j]$ нь $s_is_{i+1}... s_j$.

$s$ тэмдэгт мөр нь дараах нөхцөлүүдийг хангаж байвал "Gray" тэмдэгт мөр гэдэг:

  • -Тэмдэгт мөрийн урт $|s|$ нь сондгой.;
  • -$s_{\frac{|s|+1}{2}}$ буюу яг голын тэмдэгт нь энэ тэмдэгт мөр дотор яг ганц л байдаг;
  • -Нэг бол $|s|=1$ эсвэл $s[1...\frac{|s|+1}{2}-1]$ ба $s[\frac{|s|+1}{2}+1...|s|]$ тэмдэгт мөрүүд адилхан ба "Gray" тэмдэгт мөр.

Жишээ нь $"abacaba", "xzx", "g"$-үүд нь Gray тэмдэгт мөр ба $"aaa", "xz", "abaxcbc"$-үүд нь биш юм.

$p$ тэмдэгт мөрийн үзэмжийг $p$-н дэд тэмдэгт мөр бөгөөд "Gray" тэмдэгт мөр байдаг тэмдэгт мөрүүдийн уртуудын квадратуудын нийлбэр гэж тодорхойлъё. Өөрөөр хэлбэл $i,j$ хос бүрийн хувьд $(1\le i\le j\le |p|)$ авч үзээд $p[i... j]$ Gray тэмдэгт мөр байвал $(j - i + 1)^2$ утгыг үзэмж дээр нь нэмж тооцно.

Ксениад Англи цагаан толгойн жижиг үсгүүдээс тогтох $t$ тэмдэгт мөр өгөгдсөн. Түүнд аль нэг тэмдэгтийг дурын үсгээр солих үйлдэл зөвшөөрөгдсөн бол тэр дарааллын үзэмжийг хамгийн ихдээ хэд болгож чадах вэ?

Оролт

Нэг мөрөнд зөвхөн Англи цагаан толгойн жижиг үсгүүдээс тогтох $t (1\le |t|\le 10^5)$ тэмдэгт мөр өгөгдөнө.

Гаралт

Ксениа тэмдэгт мөрийн үзэмжийг хамгийн ихдээ хэд болгож чадах утгыг хэвлэнэ үү.

Жич: С++ хэл хэрэглэж байгаа бол 64-бит бүхэл тоог уншихдаа %lld тодорхойлогчийг ашиглахгүй байхыг зөвлөж байна. cin, cout стриймүүд эсвэл %I64d тодорхойлогчийг ашиглана уу.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
zzz
Гаралт
12
Оролт
aba
Гаралт
12
Оролт
abacaba
Гаралт
83
Оролт
aaaaaa
Гаралт
15

Тэмдэглэл

In the first test sample the given string can be transformed into string $p$ = "zbz$". Such string contains Gray strings as substrings $p[1... 1]$, $p[2... 2]$, $p[3... 3]$ и $p[1... 3]$. In total, the beauty of string $p$ gets equal to $1^{2} + 1^{2} + 1^{2} + 3^{2} = 12$. You can't obtain a more beautiful string.

In the second test case it is not necessary to perform any operation. The initial string has the maximum possible beauty.

Сэтгэгдлүүдийг ачааллаж байна...