好串的数目

题号：NC307629
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

对于一个长度为 $n$ 的字符串 $s = s_0s_1 \cdots s_{n-1}$ 来说，子串的定义是从中选出两个下标 $l, r$ $(0 \leq l \leq r \leq n-1)$ ，这之间所有的字符组合起来的一个新的字符串： $s' = s_ls_{l+1} \cdots s_r$ 就是其中一个子串。

现在给出一个只有数字字符 $0 \sim 9$ 组成的数字字符串，小蓝想要知道在其所有的子串中，有多少个子串是好串。一个子串是好串，当且仅当它满足以下两个条件之一：
1. 单字符子串一定是好串，即当子串长度为 $1$ 时，它总是好串；
2. 长度大于 $1$ 时，可以拆分为两个连续非递减子串：
一个串 $p = p_0p_1 \cdots p_{k-1}$ 为**连续非递减子串**是指，对于所有 $1 \leq i < k$ ，满足 $p_i = p_{i-1}$ 或 $p_i = p_{i-1} + 1$ 。即数字串中的每一个数字，要么等于上一个数字，要么等于上一个数字加 $1$ 。例如 `12233`、`456` 是连续非递减子串。

输入描述:

输入一行包含一个字符串 。
- 对于所有评测用例，， 中只包含数字字符 。

输出描述:

输出一行包含一个整数表示答案，即好串的数目。

示例1

输入

复制

输出

复制

说明

- 长度为  的好串：`1`、`2`、`2`、`5`、`8`，共  个；
- 长度为  的好串：`12`、`22`、`25`、`58`，共  个；
- 长度为  的好串：`122`、`225`，共  个；
- 长度为  的好串：`1225`，共  个；

总计  个。

示例2

输入

复制

输出

复制

说明

- 长度为  的好串：`9`、`7`、`8`、`5`、`6`，共  个；
- 长度为  的好串：`97`、`78`、`85`、`56`，共  个；
- 长度为  的好串：`978`、`785`、`856`，共  个；
- 长度为  的好串：`7856`，共  个；

总计  个。