F - Insert / Time Limit: 2 sec / Memory Limit: 10...

We can solve this problem by "reversing" the insertion process. Instead of simulating the insertions from 1 to $N$ (which would be too slow for $N$ up to $5\times10^5$), we can compute the final array by “placing” the numbers into the available positions.

Explanation

Imagine you have $N$ empty slots (positions $1$ to $N$). Initially, all positions are available. For each $i$ (from $1$ to $N$) the operation “insert $i$ so that it becomes the $P_i$‑th element” means that when $i$ is inserted, it is placed into the $P_i$-th available slot (if you think about the positions that are still free).

It turns out that if we process the numbers in reverse order (from $N$ down to $1$), we can decide which available slot each number must go to. In other words, for $i = N, N-1, \dots, 1$:

1. Choose the $P_i$-th available position.
2. Place the number $i$ in that position.
3. Mark that position as no longer available.

This is a standard “inverse permutation from an inversion sequence” problem.

To quickly get the $k$‑th available position we use a Fenwick Tree (Binary Indexed Tree). We initialize the tree with $1$ for every available position. Then, finding the $k$-th available position can be done in $O(\log N)$ time using a binary search over the prefix sums of the tree.

The Code

Below is the complete C++ solution that implements the above idea:

cpp
#include <iostream>
#include <vector>
using namespace std;
 
// Binary Indexed Tree (Fenwick Tree) for sum queries and point updates.
struct BIT {
    int n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) { }
    
    // Increase value at index i by delta.
    void update(int i, int delta) {
        for(; i <= n; i += i & -i)
            tree[i] += delta;
    }
    
    // Compute prefix sum for index i.
    int sum(int i) {
        int s = 0;
        for(; i > 0; i -= i & -i)
            s += tree[i];
        return s;
    }
    
    // Find smallest index such that prefix sum >= value.
    int lower_bound(int value) {
        int idx = 0;
        // For n up to 5e5, 2^19 = 524288 is enough.
        for (int bit = 1 << 19; bit; bit >>= 1) {
            int next = idx + bit;
            if(next <= n && tree[next] < value) {
                value -= tree[next];
                idx = next;
            }
        }
        return idx + 1;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    // Read P[1] to P[N] (1-indexed)
    vector<int> P(N + 1);
    for (int i = 1; i <= N; i++){
        cin >> P[i];
    }
    
    // Initialize BIT: mark all positions as available (value 1).
    BIT bit(N);
    for (int i = 1; i <= N; i++){
        bit.update(i, 1);
    }
    
    // ans[i] will hold the final number at position i.
    vector<int> ans(N + 1, 0);
    
    // Process numbers from N down to 1.
    for (int i = N; i >= 1; i--){
        // Find the P[i]-th available position.
        int pos = bit.lower_bound(P[i]);
        ans[pos] = i;       // Place number i in that position.
        bit.update(pos, -1); // Mark the position as occupied.
    }
    
    // Output the final array.
    for (int i = 1; i <= N; i++){
        cout << ans[i] << (i == N ? "\n" : " ");
    }
    
    return 0;
}

How the Code Works

1. Input Reading:
   We read the integer $N$ and the $P_i$ values. Note that the $P$ array is stored using 1-indexing for easier matching with our BIT implementation.

2. BIT Initialization:
   We create a BIT of size $N$ and initialize all positions with value $1$ (indicating that all positions are initially available).

3. Reverse Processing:
   We iterate from $i = N$ down to $1$. For each $i$:

   • We find the $P_i$-th available position using the lower_bound function.
   • Place $i$ into that position.
   • Update the BIT to mark that position as no longer available.

4. Output:
   Finally, we output the constructed array.

This solution runs in $O(N \log N)$ time and uses $O(N)$ memory, which is efficient given the constraints.