Description

继syuct- acm队伍中王木辛r发明了时光机之后，王大头对此感到新奇，王大头想乘坐时光机看看2077年的世界，但是王大头不知道的是，王木辛r在发明时光机的时候，将他的影分身留在了时光机之中（因为王木辛r始终算不出来这道题的答案，所以留下了影分身在时光机中想找有缘人解决掉这个问题），只有回答对了王木辛r的影分身的题目，才可以穿越到你想要到达的时间。王大头想让你帮助他一起解决这个问题。(因为王大头也不会）

影分身给了你一个长度为n的数组a，他想知道有多少个三元组（i,j,k）满足ai*aj=ak;

Format

Input

输入的第一行包含一个整数n（1≤n≤1e6）

第二行输入包含n个整数a1,a2,a3...an（1≤ai≤1e6）

Output

输出单个整数，表示三元组的个数。

Samples

3
1 1 1

27

5
1 2 4 8 16

15

Hint

善良的王木辛r的影分身告诉你：可爱的评测机1s只可以测试1e7-1e8左右的数据

如果你帮助王大头写的代码的时间复杂度远远大于1e7-1e8可是会tle的哦~~~