#include <bits/stdc++.h>
using namespace std;
// ----- Judge-provided API (do not modify these signatures) -----
pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0);
// ======================================================================
// If you want to test locally with the sample grader format, you can
// compile with -DLOCAL and provide a simple simulator below.
// Comment this whole LOCAL block out on the real judge.
// ======================================================================
#ifdef LOCAL
static int gN;
static vector<long long> gP; // true prices
static long long gP0;
pair<vector<int>, long long> transaction(long long M) {
// Validate constraints
long long P0 = gP[0];
long long Pmin = gP.back();
if (!(P0 > M && M >= Pmin)) {
cerr << "Invalid argument in transaction: M=" << M << " P0=" << P0 << " Pmin=" << Pmin << "\n";
exit(0);
}
long long pile = M;
vector<int> L;
for (int i = 0; i < gN; ++i) {
if (pile >= gP[i]) {
if (i == 0) { // should never happen since M < P0
// no-op, but guard
}
pile -= gP[i];
L.push_back(i);
}
}
// The problem says L is returned in increasing order (we already add in increasing i)
return {L, pile};
}
// A small local main for testing: reads full P, then runs our solution and prints counts.
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> gN;
gP.resize(gN);
for (int i = 0; i < gN; ++i) cin >> gP[i];
gP0 = gP[0];
// We'll wrap the counting by intercepting transaction calls:
// Track counts per type as we go to print final answer like the sample grader expects.
static vector<long long> buyCount;
buyCount.assign(gN, 0);
// Interpose transaction to count
auto orig_transaction = transaction;
function<pair<vector<int>, long long>(long long)> hooked = [&](long long M) {
auto res = orig_transaction(M);
for (int x : res.first) buyCount[x]++;
return res;
};
// Replace the global function pointer (simulate by capturing lambda in a wrapper)
// In this simple LOCAL harness, we just shadow the name via another function.
// We'll provide a local alias and call that in buy_souvenirs_local.
// To avoid refactoring, define a macro to redirect:
#undef transaction
#define transaction(M) hooked(M)
buy_souvenirs(gN, gP0);
for (int i = 0; i < gN; ++i) {
if (i) cout << ' ';
cout << buyCount[i];
}
cout << "\n";
return 0;
}
#endif
// ======================================================================
// Helper: simulate a transaction for a *candidate* price array P with M
static pair<vector<int>, long long> simulate_with_P(const vector<long long>& Pcand, long long M) {
long long pile = M;
vector<int> L;
int N = (int)Pcand.size();
for (int i = 0; i < N; ++i) {
if (pile >= Pcand[i]) {
pile -= Pcand[i];
L.push_back(i);
}
}
return {L, pile};
}
void buy_souvenirs(int N, long long P0) {
// Target counts: q[i] = i, and q[0] = 0
vector<int> need(N, 0);
for (int i = 1; i < N; ++i) need[i] = i;
// Current counts (we'll update as we transact)
vector<int> got(N, 0);
// Build all candidate price sequences consistent with constraints:
// P[0] = P0, strictly decreasing, each P[i] in [1..10], distinct.
// So pick N-1 distinct numbers from [1..P0-1], sort descending, append P0 at front.
vector<vector<long long>> candidates;
vector<int> vals;
for (int v = 1; v <= (int)P0 - 1; ++v) vals.push_back(v);
// choose N-1 of these
// we select combinations in descending order later
int K = (int)vals.size();
if (N - 1 > K) {
// invalid input combo; but assume judge inputs are valid
} else {
vector<int> mask(K, 0);
fill(mask.begin(), mask.begin() + (N - 1), 1);
do {
vector<int> pick;
for (int i = 0; i < K; ++i) if (mask[i]) pick.push_back(vals[i]);
sort(pick.begin(), pick.end(), greater<int>());
vector<long long> P;
P.reserve(N);
P.push_back(P0);
for (int x : pick) P.push_back(x);
// ensure strictly decreasing
bool ok = true;
for (int i = 0; i + 1 < N; ++i) if (!(P[i] > P[i + 1])) ok = false;
if (ok) candidates.push_back(P);
} while (prev_permutation(mask.begin(), mask.end()));
}
// Known (agreed) prices (excluding P0 which is known)
vector<long long> knownP(N, -1);
knownP[0] = P0;
auto recompute_agreed = [&]() {
// For each i, if all candidates have same P[i], set knownP[i]
for (int i = 1; i < N; ++i) {
long long v = candidates[0][i];
bool same = true;
for (size_t c = 1; c < candidates.size(); ++c) {
if (candidates[c][i] != v) { same = false; break; }
}
if (same) knownP[i] = v;
}
};
recompute_agreed();
auto all_done = [&]() {
for (int i = 1; i < N; ++i) if (got[i] < need[i]) return false;
return true;
};
// Helper: attempt to finish purchasing type i using known price
auto finish_type_if_known = [&](int i) {
if (i == 0) return;
if (knownP[i] != -1) {
int rem = need[i] - got[i];
while (rem > 0) {
auto [L, R] = transaction(knownP[i]); // buys exactly type i, once
(void)R;
for (int x : L) got[x]++;
rem--;
}
}
};
// While we still have ambiguity or unfinished counts, keep going
while (!all_done()) {
// Finish any type whose price is known (and still has remaining need)
bool progressed = false;
for (int i = 1; i < N; ++i) {
if (knownP[i] != -1 && got[i] < need[i]) {
finish_type_if_known(i);
progressed = true;
}
}
if (all_done()) break;
// Check if all prices known
bool all_prices_known = true;
for (int i = 1; i < N; ++i) if (knownP[i] == -1) { all_prices_known = false; break; }
if (all_prices_known) {
// Just finish any leftovers
for (int i = 1; i < N; ++i) finish_type_if_known(i);
break;
}
// Choose a SAFE M (valid for all remaining candidates) that:
// (1) doesn't exceed remaining capacities for any candidate,
// (2) splits candidates as much as possible.
long long lowerSafe = 0;
for (auto &Pc : candidates) lowerSafe = max(lowerSafe, Pc.back()); // max Pmin among candidates
long long upperSafe = P0 - 1;
// Precompute candidate outputs per M and whether they are capacity-safe
struct Key {
vector<int> L;
long long R;
bool operator<(Key const& o) const {
if (R != o.R) return R < o.R;
return L < o.L;
}
};
long long bestM = -1;
int bestDiversity = -1;
for (long long M = lowerSafe; M <= upperSafe; ++M) {
bool capacity_ok = true;
map<Key, int> bucket;
for (auto &Pc : candidates) {
auto [L, R] = simulate_with_P(Pc, M);
// capacity check: this transaction should not cause any got[i] to exceed need[i]
bool ok_for_this_candidate = true;
// NOTE: Type 0 must never be included since M < P0; simulation respects that.
for (int i : L) {
if (got[i] + 1 > need[i]) { ok_for_this_candidate = false; break; }
}
if (!ok_for_this_candidate) { capacity_ok = false; break; }
bucket[{L, R}]++;
}
if (!capacity_ok) continue;
int diversity = (int)bucket.size();
if (diversity > bestDiversity) {
bestDiversity = diversity;
bestM = M;
}
}
if (bestM == -1) {
// No safe discriminating M found that respects capacities.
// Fall back: try to *force* agreement by finishing any single type whose price
// is agreed (if any remaining). If none, pick the smallest i with the smallest
// agreed price across candidates (they must agree on some price eventually).
// In practice with tiny domains, there will be an agreed price quickly. But just in case:
bool did_any = false;
recompute_agreed();
for (int i = 1; i < N; ++i) {
if (knownP[i] != -1 && got[i] < need[i]) {
finish_type_if_known(i);
did_any = true;
}
}
if (did_any) continue;
// As a last resort: pick an i such that *all candidates* have the same P[i]
// (this is what knownP tracks); if none exist (extremely unlikely here), just
// pick M = lowerSafe to continue; capacity shouldn’t be violated since we already tried.
for (int i = 1; i < N; ++i) {
if (knownP[i] != -1 && got[i] < need[i]) {
finish_type_if_known(i);
did_any = true;
break;
}
}
if (did_any) continue;
// If still stuck, just transact at lowerSafe once (it’s valid),
// but **guard** to ensure no capacity overflow in the actual result.
auto [L, R] = transaction(lowerSafe);
bool real_ok = true;
for (int x : L) if (got[x] + 1 > need[x]) real_ok = false;
if (!real_ok) {
// Should not happen under constraints/logic above.
// To be safe, do a known price if any (even if none earlier).
// Find the smallest i where all candidates have the same P[i].
recompute_agreed();
bool did = false;
for (int i = 1; i < N; ++i) {
if (knownP[i] != -1 && got[i] < need[i]) {
finish_type_if_known(i);
did = true;
break;
}
}
if (!did) {
// As absolute fallback (shouldn’t be reached), pick the smallest i that still has room
// and use the *minimum* possible price among candidates for that i (guaranteed >= Pmin)
// so M will be valid. This preserves safety; it might not discriminate candidates well,
// but we’ll keep moving and stay within capacities.
int target = -1;
for (int i = 1; i < N; ++i) if (got[i] < need[i]) { target = i; break; }
long long m_guess = LLONG_MAX;
for (auto &Pc : candidates) m_guess = min(m_guess, Pc[target]);
auto [L2, R2] = transaction(m_guess);
for (int x : L2) got[x]++;
// filter candidates
vector<vector<long long>> next;
for (auto &Pc : candidates) {
auto [LL, RR] = simulate_with_P(Pc, m_guess);
if (LL == L2 && RR == R2) next.push_back(Pc);
}
candidates.swap(next);
recompute_agreed();
continue;
}
continue;
} else {
for (int x : L) got[x]++;
// filter candidates by the real observation we just made
vector<vector<long long>> next;
for (auto &Pc : candidates) {
auto [LL, RR] = simulate_with_P(Pc, lowerSafe);
if (LL == L && RR == R) next.push_back(Pc);
}
candidates.swap(next);
recompute_agreed();
continue;
}
}
// Perform the chosen bestM, update counts, and filter candidates
auto [Lreal, Rreal] = transaction(bestM);
for (int x : Lreal) got[x]++;
vector<vector<long long>> next;
for (auto &Pc : candidates) {
auto [LL, RR] = simulate_with_P(Pc, bestM);
if (LL == Lreal && RR == Rreal) next.push_back(Pc);
}
candidates.swap(next);
recompute_agreed();
}
// If anything left (shouldn’t be), finish with known prices
for (int i = 1; i < N; ++i) {
while (got[i] < need[i]) {
long long M = knownP[i];
if (M == -1) {
// if somehow unknown, pick it from the (now tiny) candidate set
M = candidates[0][i];
knownP[i] = M;
}
auto [L, R] = transaction(M);
(void)R;
for (int x : L) got[x]++;
}
}
}
