[蓝桥杯 2023 省 A] 更小的数

题目描述

小蓝有一个长度为 $n$ 的数字字符串。小蓝可以选择其中一段连续子串，将这一段中的字符顺序反转，其他位置保持不变。

请统计有多少个不同的区间，使反转该区间后得到的新数字字符串严格小于原字符串。选择长度为 $1$ 的区间也是允许的，但这种反转不会改变字符串，因此不会计入答案。

输入格式

输入一行一个只包含数字字符的字符串。

输出格式

输出一个整数，表示满足条件的区间数量。

样例输入

210102

样例输出

8

数据范围与约定

对于 $20\%$ 的数据，$n\le 100$。

对于 $40\%$ 的数据，$n\le 1000$。

对于全部数据，$1\le n\le 5000$。

题目来源：洛谷 P9232