Muua打算开一间商店!
要管理一间店,最重要的事就是库存管理了。对于某一种商品,Muua按时间顺序记录了它的进货
(用+表示)和出售(用-表示)的情况。例如,++-+--表示,进了2件这种商品,卖出了1件,又进
了1件,又卖出了2件。
特别地,每天的记录序列都满足某些条件。具体来说,包括以下几点:
• 每次出售商品时,库存中要有商品。例如记录+--不满足这一点。
• 结束营业时,库存刚好卖空。例如记录+-+不满足这一点。
+-++--就是一个满足所有要求的记录序列。
不幸的是,Muua在记录时忘了把不同的日期分开。最后,她的账本上只记下了一长串由+和-组成的字
符串S。请你帮忙看看,这个字符串中有多少子串是某一天合法的记录序列?
输出1行1个整数,表示S中有多少子串是某一天合法的记录序列。
约定
对于前40%的数据,|S| ≤ 3000。
在第一组样例中,子串+-和++--是合法的记录序列。
字符串的子串是原串中一段连续字符形成的字符串。例如,aacd的子串有a、ac、aacd等等,
但ca、ad不是aacd的子串。