该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

给定一个长度为 $n$ 的数组 $a$，求

$ \sum_{i = 1} ^ {n}\sum_{j = i + 1} ^ {n}[a_j \mid a_i ^ 2] $。

Format

Input

输入的第一行包含一个正整数 $n (1 \le n \le 10 ^ 5)$。

输入的第二行包含 $n$ 个随机正整数 $a_i(1 \le a_i \le 10 ^ 6)$。

Output

输出满足要求的数对个数。

Samples

5
9 4 3 2 1

6

Limitation

1s, 1024KiB for each test case.