# CFR 806 E. Blog Post Rating ( Segment Tree, Fenwick Tree )

Problem - E - Codeforces
りんごさんの提出見て回答。

The first line contains a single integer n (1 ≤ n ≤ 5e5) — the number of Codeforces users.
The second line contains n integers a1, a2, ..., an ( - 5e5 ≤ ai ≤ 5e5) — estimated blog post ratings for users in order from 1 to n.

O( N lg A ) / O( N )

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

const int MAXN = int( 5e5 );
const int MAXA = int( 5e5 ); // abs

int N;
int A[ MAXN ];

int ftree[ MAXA * 2 + 1 + 1 ];
void add( int x, int v ) {
for( int i = x; i < MAXA * 2 + 1 + 1; i += i & -i ) {
ftree[ i ] += v;
}
}
int sum( int x ) {
int res = 0;
for( int i = x; i; i -= i & -i ) {
res += ftree[ i ];
}
return res;
}

struct segt {
int minv[ MAXA * 2 + 1 << 2 ];
int tag[ MAXA * 2 + 1 << 2 ];
void push( int t ) {
minv[ t << 1 ] += tag[ t ];
tag[ t << 1 ] += tag[ t ];
minv[ t << 1 | 1 ] += tag[ t ];
tag[ t << 1 | 1 ] += tag[ t ];
tag[ t ] = 0;
}
void pull( int t ) {
minv[ t ] = min( minv[ t << 1 ], minv[ t << 1 | 1 ] );
}
void add( int ql, int qr, int v, int lb = 0, int rb = MAXA * 2 + 1, int t = 1 ) {
if( qr <= lb or rb <= ql ) return;
if( ql <= lb and rb <= qr ) {
minv[ t ] += v;
tag[ t ] += v;
return;
}
push( t );
int mid = lb + rb >> 1;
add( ql, qr, v, lb, mid, t << 1 );
add( ql, qr, v, mid, rb, t << 1 | 1 );
pull( t );
}
int qmin( int ql, int qr, int lb = 0, int rb = MAXA * 2 + 1, int t = 1 ) {
if( qr <= lb or rb <= ql ) return 0x3f3f3f3f;
if( ql <= lb and rb <= qr ) return minv[ t ];
push( t );
int mid = lb + rb >> 1;
int res = min( qmin( ql, qr, lb, mid, t << 1 ), qmin( ql, qr, mid, rb, t << 1 | 1 ) );
pull( t );
return res;
}
} root;

signed main() {
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ) {
cin >> A[ i ];
A[ i ] += MAXA; // [ - MAXA, MAXA ] -> [ 0, MAXA * 2 ]
}
for( int i = 0; i <= MAXA * 2; ++i ) {
root.add( i, i + 1, i );
}
for( int i = 0; i < N; ++i ) {
add( A[ i ] + 1, 1 ); // -> [ 1, MAXA * 2 + 1 ]
root.add( 0, A[ i ], 1 );
int lb = 0, ub = MAXA;
int x = MAXA;
while( lb <= ub ) {
int mid = lb + ub >> 1;
if( sum( mid + 1 ) >= MAXA - mid ) {
x = mid;
ub = mid - 1;
} else {
lb = mid + 1;
}
}
cout << root.qmin( x, MAXA * 2 + 1 ) - MAXA << "\n";
}
return 0;
}
```