Cod sursa(job #936573)
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
const int NMAX = 100011;
int f[NMAX];
vector<int> v, TopMax;
inline void output(ostream& out, int x)
{
if(-1 == x) return;
output(out, f[x]);
out << v[x] << ' ';
}
int main()
{
int N, i, left, middle, right;
ifstream in("scmax.in");
ofstream out("scmax.out");
in >> N;
v.reserve(N);
copy(istream_iterator<int>(in), istream_iterator<int>(), v.begin());
TopMax.push_back(0);
for(i = 1; i < N; ++i)
{
f[i] = -1;
if(v[i] == v[TopMax.back()]) continue;
if(v[TopMax.back()] < v[i])
{
f[i] = TopMax.back();
TopMax.push_back(i);
continue;
}
left = 0; right = TopMax.size() - 1;
while(left <= right)
{
middle = (left + right) >> 1;
if(v[i] == v[TopMax[middle]])
{
break;
}
if(v[i] >= v[TopMax[middle]]) left = middle + 1;
else right = middle - 1;
}
if(left <= right) continue;
if(v[TopMax[left]] > v[i])
{
if(left) f[i] = TopMax[left - 1];
TopMax[left] = i;
}
}
out << TopMax.size() << '\n';
output(out, TopMax.back());
out << '\n';
return EXIT_SUCCESS;
}