#include "souvenirs.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<int> P(N), cnt(N); P[0] = P0; cnt[0] = 1;
FOR(i, 1, N - 1) {
if(P[i] != 0) {
REP(j, max(0, i - cnt[i])) transaction(P[i]);
} else {
pair<vector<int>, long long> s = transaction(P[i - 1] - 1);
if((int)s.first.size() == 1) {
if(s.second == 0) P[i] = P[i - 1] - 1;
else P[i] = P[i - 1] - 2;
} else if((int)s.first.size() == 2) {
P[i] = P[i - 1] - 2; P[i + 1] = 1;
}
FORE(it, s.first) cnt[*it]++;
}
}
return;
}
