题目描述

阿玛鲁正在一家外国商店购买纪念品。商店里有 $N$ 种 纪念品，每种纪念品都有无限多个。

每种纪念品都有固定的价格。具体来说，第 $i$ 种（$0 \leq i < N$）纪念品的价格为 $P[i]$ 枚硬币，其中 $P[i]$ 是正整数。

阿玛鲁知道纪念品的价格按种类序号递减排列，且所有价格都是不同的。具体地，$P[0] > P[1] > \cdots > P[N - 1] > 0$。此外，他还知道 $P[0]$ 的值。但遗憾的是，阿玛鲁对其他纪念品的价格一无所知。

为了购买一些纪念品，阿玛鲁会与卖家进行若干次交易。

每次交易包括以下步骤：

1. 阿玛鲁交给卖家若干（正数）枚硬币。
2. 卖家将这些硬币放在里屋的桌子上堆成一堆，阿玛鲁看不到。
3. 卖家依次考虑第 0、1、……、$N-1$ 种纪念品，每种在每次交易中恰好被考虑一次。
   • 当考虑第 $i$ 种纪念品时，如果堆中当前的硬币数量不少于 $P[i]$，那么：
     • 卖家从堆中取出 $P[i]$ 枚硬币。
     • 卖家在桌上放一个第 $i$ 种纪念品。
4. 卖家将堆中剩余的所有硬币以及桌上的所有纪念品交给阿玛鲁。

注意，每次交易开始前，桌子上没有硬币和纪念品。

你的任务是指导阿玛鲁进行若干次交易，使得：

• 每次交易中他至少购买一个纪念品。
• 总体上，对于每个 $0 \leq i < N$，他恰好购买 $i$ 个第 $i$ 种纪念品。注意，这意味着阿玛鲁不应该购买任何第 0 种纪念品。

阿玛鲁不需要尽量减少交易次数，且他拥有无限的硬币供应。

实现细节

你需要实现以下函数：

void buy_souvenirs(int N, long long P0)

• $N$：纪念品的种类数。
• $P0$：$P[0]$ 的值。

上述函数可以调用以下函数来指导阿玛鲁进行交易：

std::pair<std::vector<int>, long long> transaction(long long M)

• $M$：阿玛鲁交给卖家的硬币数量。
• 该函数返回一个 pair。pair 的第一个元素是数组 $L$，包含所购买纪念品的种类（按递增顺序排列）。第二个元素是整数 $R$，即交易后返还给阿玛鲁的硬币数量。
• 要求满足 $P[0] > M \geq P[N - 1]$。$P[0] > M$ 确保阿玛鲁不会购买第 0 种纪念品，$M \geq P[N - 1]$ 确保阿玛鲁至少购买一个纪念品。如果不满足这些条件，你的解决方案将得到“Output isn't correct: Invalid argument”的判定。注意，与 $P[0]$ 不同，$P[N - 1]$ 的值并未在输入中提供。
• 每个测试用例中，该函数最多可被调用 5000 次。

评测器的行为不是自适应的。这意味着价格序列 $P$ 在调用 buy_souvenirs 之前就已固定。

输入格式

N
P[0] P[1] ... P[N-1]

输出格式

Q[0] Q[1] ... Q[N-1]

其中 $Q[i]$ 是购买的第 $i$ 种纪念品的总数。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

示例

考虑以下调用：

buy_souvenirs(3, 4)

这里 $N = 3$ 种纪念品，且 $P[0] = 4$。可能的价格序列 $P$ 只有三种：$[4, 3, 2]$、$[4, 3, 1]$ 和 $[4, 2, 1]$。

假设 buy_souvenirs 调用 transaction(2)，返回 $([2],1)$，这意味着阿玛鲁购买了一个第 2 种纪念品，卖家返还给他 1 枚硬币。由此我们可以推断出 $P = [4,3,1]$，因为：

• 对于 $P = [4,3,2]$，transaction(2) 会返回 $([2],0)$。
• 对于 $P = [4,2,1]$，transaction(2) 会返回 $([1],0)$。

然后 buy_souvenirs 可以调用 transaction(3)，返回 $([1],0)$，即阿玛鲁购买了一个第 1 种纪念品，卖家返还 0 枚硬币。到目前为止，他总共购买了 1 个第 1 种纪念品和 1 个第 2 种纪念品。

最后，buy_souvenirs 可以调用 transaction(1)，返回 $([2],0)$，即购买了一个第 2 种纪念品。注意，这里也可以使用 transaction(2)。此时，阿玛鲁总共购买了 1 个第 1 种纪念品和 2 个第 2 种纪念品，满足要求。

约束条件

• $2 \leq N \leq 100$
• 对于每个 $0 \leq i < N$，$1 \leq P[i] \leq 10^{15}$。
• 对于每个 $0 \leq i < N - 1$，$P[i] > P[i + 1]$。

子任务

子任务	分值	附加约束
1	4	$N=2$
2	3	对于每个 $0 \leq i < N$，$P[i]=N-i$。
3	14	对于每个 $0 \leq i < N-1$，$P[i] \leq P[i+1] + 2$。
4	18	$N=3$
5	28	对于每个 $0 \leq i < N-2$，$P[i+1] + P[i+2] \leq P[i]$；对于每个 $0 \leq i < N-1$，$P[i] \leq 2 \cdot P[i+1]$。
6	33	无附加约束。