Cod sursa(job #828827)
#include <fstream>
using namespace std;
#define NMAX 100001
ifstream fin("Scmax.in");
ofstream fout("Scmax.out");
int n, best = -1;
int a[NMAX], prev[NMAX], minn[NMAX];
bool viz[NMAX];
void Search( int st, int dr, int val );
void Print( int val, int i );
int main()
{
fin >> n;
for( int i = 1; i <= n; ++i )
{
fin >> a[i];
Search( 0, n, i );
}
fout << best + 1 << '\n';
Print( minn[best], best );
fin.close();
fout.close();
return 0;
}
void Search( int l, int r, int val )
{
while( l != r )
{
int mid = (l + r)/2;
if( viz[mid] == true && a[val] > a[minn[mid]] )
l = mid + 1;
else
r = mid;
}
if( l > 0 )
prev[val] = minn[l-1];
if( viz[r] == false || a[minn[l]] > a[val] )
{
minn[l] = val;
viz[l] = true;
if( l > best )
best = l;
}
}
void Print( int val, int i )
{
if( i >= 0 )
{
Print( prev[val], i-1 );
fout << a[val];
if( i < best )
fout << ' ';
}
}