题目描述

对于一个长度为 $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 是连续非递减子串。

输入格式

输入一行包含一个字符串 $s$。

输出格式

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

12258

12

97856

13

提示

样例说明 1

• 长度为 $1$ 的好串：1、2、2、5、8，共 $5$ 个；
• 长度为 $2$ 的好串：12、22、25、58，共 $4$ 个；
• 长度为 $3$ 的好串：122、225，共 $2$ 个；
• 长度为 $4$ 的好串：1225，共 $1$ 个；

总计 $5 + 4 + 2 + 1 = 12$ 个。

样例说明 2

• 长度为 $1$ 的好串：9、7、8、5、6，共 $5$ 个；
• 长度为 $2$ 的好串：97、78、85、56，共 $4$ 个；
• 长度为 $3$ 的好串：978、785、856，共 $3$ 个；
• 长度为 $4$ 的好串：7856，共 $1$ 个；

总计 $5 + 4 + 3 + 1 = 13$ 个。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq n \leq 5$；
• 对于 $40\%$ 的评测用例，$1 \leq n \leq 20$；
• 对于 $60\%$ 的评测用例，$1 \leq n \leq 100$；
• 对于 $70\%$ 的评测用例，$1 \leq n \leq 10^3$；
• 对于 $80\%$ 的评测用例，$1 \leq n \leq 10^4$；
• 对于所有评测用例，$1 \leq n \leq 10^5$，$s$ 中只包含数字字符 $0 \sim 9$。