You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 ROIR 2020 Day2 T3. Банкомат,译者ksyx

你正在开发一个多面额 ATM，称为 Universal ATM。具体地说，现在有 $n$ 种升序排序的面额分别为 $a_1,~a_2,~\ldots,~a_n$ 的纸币，即对于 $i>2$，有 $a_{i-1}<a_i$。除此之外，还保证 $a_1=1$。

假设客户要取总额为 $c$ 的纸币，你开发的 ATM 将使用如下算法进行纸币的分配：每次选取一个选取后发给用户的总金额不超过 $c$ 最大面额，直至总金额达到 $c$。因为存在面额为 $1$ 的纸币，我们可以发现这个算法总是能够结束。

为了评估这个算法的效率，你想知道对于总额不超过 $b$ 的请求最大需要多少张纸币。因为业务场景不同，你总共需要回答 $q$ 个场景下的询问 $b_1,~b_2,~\ldots,~b_q$。

你的任务是编写一个程序，根据给出的面额列表确定在不同业务场景下最大需要多少张纸币。

输入格式

第一行一个整数 $n$，表示面额的数量。

接下来一行 $n$ 个整数 $a_i$。

第三行一个整数 $q$，表示询问的数量。

接下来 $q$ 行每行一个整数 $b_i$。

输出格式

对于每一个询问，输出两个整数，分别表示取出纸币数量最多的情况下客户取出的总额和取出纸币的数量。如果多个不超过输入中最大总额的取款请求都对应这个纸币数量，输出任意一个。

4
1 5 10 50
3
2
8
50

2 2
8 4
49 9

提示

【样例 1 解释】

各个询问的一种可行解如下：

$2=1+1$，$8=5+1+1+1$，$49=10+10+10+10+5+1+1+1+1$。

【数据范围】

对于 $100\%$ 的数据，有 $1\le n\le 2\times 10^5,~$$1=a_1<a_2<\ldots<a_n\le10^{18},~$$1\le q\le 2\times 10^5,~$$1\le b_i\le 10^8$。

各子任务详情如下：