CF691F Couple Cover

“Couple Cover”是一款极受欢迎的基于运气的游戏，即将开始！两名玩家必须协作组成一个矩形。桌子上有一个装有 $n$ 个球的袋子，每个球上写有一个整数。第一位玩家随机摸出一个球（每个球被选中的概率均等）——该球上的数字即为矩形的宽（单位为米）。该球不会放回，然后第二位玩家从袋子中再随机摸出一个球——该球上的数字即为矩形的高（单位为米）。如果该矩形的面积大于等于某个阈值 $p$（单位为平方米），两位玩家就获胜。否则，两人失败。 游戏的组织者正在为 $p$ 选择一个合适的值，使得情侣获胜的概率既不会太高也不会太低，但他们计算速度很慢，于是请你帮忙解答他们的一些问题。你将得到所有球上的数字列表，组织者想知道对于若干不同的 $p$ 值，有多少种获胜的球对。注意，如果某一对中第一个球或第二个球不同，则这两对球被认为是不同的，即使球上的数字相同也算作不同的球。

输入的第一行为一个正整数 $n$（$1\le n\le 10^6$）。 第二行为 $n$ 个正整数，第 $i$ 个数字为 $a_i$（$1\le a_i\le 3\cdot 10^6$），即第 $i$ 个球上写的数字。 第三行为一个整数 $m$（$1\le m\le 10^6$），表示需要回答的问题数量。 第四行为 $m$ 个正整数，第 $j$ 个数字为 $p_j$（$1\le p_j\le 3\cdot 10^6$），即第 $j$ 个问题对应的阈值 $p$。

对于每一个问题，输出一行，表示对于给定的 $p$ 值，可以组成多少种获胜的球对。

由 ChatGPT 5 翻译