# POI 2 Stage 3 Coding of Permutations ( Fenwick Tree, Binary Search )

http://main.edu.pl/en/archive/oi/2/kod

In the first line of the standard input there is a positive integer 30000. It is the number of elements of the sequence B.
In each of the following lines there is one nonnegative integer not greater than 30000. It is the successive element of the sequence B.

O( N lg N ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30000;

int N;
int B[ MAXN + 1 ];
int A[ MAXN + 1 ];

int ftree[ MAXN + 1 ];

void add( int x, int v ){
for( int i = x; i <= N; i += i & -i ){
ftree[ i ] += v;
}
}

int kth( int v ){
int x = 0;
for( int i = 1 << 31 - __builtin_clz( N ); i; i >>= 1 ){
if( x + i <= N and ftree[ x + i ] < v ){
v -= ftree[ x + i ];
x += i;
}
}
return x + 1;
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 1; i <= N; ++i ){
cin >> B[ i ];
}
for( int i = N; i >= 1; --i ){
if( B[ i ] >= i ){
cout << "NIE\n";
exit( 0 );
}
A[ i ] = kth( i - B[ i ] ); // 1 base kth smallest
add( A[ i ], -1 );
}
for( int i = 1; i <= N; ++i ){
cout << A[ i ] << "\n";
}
return 0;
}
```