题目描述

农场主约翰的农场布局非常独特，有一条大圆形道路围绕着他的牧场，而他的奶牛白天就在这个牧场上吃草。每天早上，奶牛们会穿过这条路走向牧场，晚上它们会再次穿过这条路，离开牧场返回牛棚。

众所周知，奶牛是习惯性的动物，每天它们都会以相同的方式穿过这条路。每头奶牛进入牧场的点和离开牧场的点都不同，并且这些穿越点彼此都不相同。农场主约翰正好有26头奶牛，他懒得为它们起名字，就直接用A到Z来命名（他还不确定如果将来再多一头牛该怎么办...），所以在这条道路周围有准确的52个穿越点。约翰通过顺时针扫描记录这些穿越点，并将每个穿越点对应的奶牛名字记下，最终形成一个包含52个字符的字符串，其中每个字母恰好出现两次。他没有记录哪些穿越点是入口，哪些是出口。

看着穿越点的地图，约翰很好奇各种奶牛对在一天中相遇的次数。如果奶牛a从入口到出口的路径与奶牛b从入口到出口的路径相交，则称奶牛（a，b）为"相交"对。请帮约翰计算相交对的总数。

输入格式

输入由一行字符串组成，包含52个大写字母。每个字母恰好出现两次。

输出格式

请输出相交对的总数。

输入样例：

ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ

输出样例：

1

思考

你能写出$O(N^4)$和$O(N^2)$两种时间复杂度的代码吗？N是牛的数量。