※ 简洁题意在分隔线下方
伸展树用两根手指指向一条有 $n$ 个珠子的彩珠链子，夸张地做了个旋转的动作。那链子被赋予生命般舞动起来，折出四散的溢彩流光，衔接成了一个环形。「这是最后一条，这样生日会场就布置完了。非旋 treap 做得到吗？」语气中莫名的愉悦在少女回头时戛然而止，「 sgt 你在干什么？你不是因为我当时的敲诈…不，帮助，而对我怀恨在心吧？」
见伸展树转过头，满脸无辜的替罪羊树停下手上的动作，倒数第二个彩珠环裂成几段掉在地上：「我记得 kdt 更喜欢三角形…而且强迫症不允许我看到相同颜色的珠子出现在同一段上。」后一句的话音微不可闻。
伸展树剜了替罪羊树一眼，又以要杀人的眼神看了看前面已经全部被改造成三角形的环，叹了口气：「就是说，把这个环拆成三段，每段长度按珠子数量来算，使它们作为三条边可以拼成三角形，并且段内没有重复的颜色？那我就勉为其难地统一一下吧。…比起这个，为什么现在还没有第三个人到会场？」
「因为新一代的题目向我们宣战了。」替罪羊树展示出传来的新闻，平淡地复读顶端的标题，「一直没想出怎么和你说，就想着之后再…」话音未落，她便被火冒三丈的伸展树吊在了挂彩珠的墙上。
你对这个种族面临的战争毫无兴趣，只想知道最后一个彩环的合法拆分方案数，也就是说——
简洁题意：
有一个环 $a[1\dots n]$ ，求把它分成三段，使得每一段内无重复元素，且三段长度可以作为某个三角形的三边的方案数。
一个拆分方案可以看作一个三元组 $(a,b,c)$ ，其中 $0\lt a\lt b \lt c\le n$ ，表示在第 $a,b,c$ 个位置之前断开。两个拆分不同当且仅当其对应的三元组不同。
Comet OJ