Pagini recente » Cod sursa (job #2252360) | Cod sursa (job #2611781) | Cod sursa (job #610379) | Cod sursa (job #2168316) | Cod sursa (job #1674810)
#include <cstdio>
#include <algorithm>
#include <set>
#define f first
#define s second
using namespace std;
multiset < pair <int, int> > st, sett;
int v[5010], poz[5010], to[5010];
bool start[5010];
int main ()
{
freopen ("subsir2.in", "r", stdin);
freopen ("subsir2.out", "w", stdout);
int n;
scanf ("%d", &n);
for (int i = 1; i <= n; ++i)
scanf ("%d", &v[i]);
for (int i = n; i; --i)
{
auto it = st.lower_bound ({v[i], -1});
if (it == st.end ()) poz[i] = 1, to[i] = -1, start[i] = true, sett.emplace (v[i], i), st.emplace_hint (st.end (), v[i], i);
else
{
int val, p;
tie (val, p) = *it;
auto itt = sett.lower_bound ({v[i], -1});
for (; itt != sett.end ();)
start[(*itt).s] = false, itt = sett.erase (itt);
sett.emplace (v[i], i);
poz[i] = poz[p] + 1;
to[i] = p;
start[i] = true;
st.emplace_hint (--it, v[i], i);
}
}
int mi = 20000000, pos;
for (int i = 1; i <= n; ++i)
if (start[i] && (poz[i] < mi || (poz[i] == mi && v[i] < v[pos]))) mi = poz[i], pos = i;
printf ("%d\n", mi);
for (; pos != -1; pos = to[pos])
printf ("%d ", pos);
printf ("\n");
return 0;
}