Pagini recente » Cod sursa (job #816948) | Cod sursa (job #3209966) | Cod sursa (job #235468) | Cod sursa (job #3134489) | Cod sursa (job #458380)
Cod sursa(job #458380)
#include <cstdio>
#define N 1000003
int n,i,v[5004],x[5004],l[5004],j,sol,min=N;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i) scanf ("%d",&v[i]);
min=-N;
for (i=n;i>0;--i)
if (v[i]>min)
x[i]=1,min=v[i];
sol=-1;
min=N;
for (i=1;i<=n;++i)
if (v[i]<min)
l[i]=-1,min=v[i];
for (i=n-1;i>0;--i)
{
int max=N,ord=0;
if (x[i]==0)
{
min=N;
for (j=i+1;j<=n;++j)
{
if ((min>v[j]) && (v[j]>v[i]) && (x[j]<=max))
{
if (x[j]<max)
max=x[j],ord=j; else
ord=j;
}
if ((v[j]<min) && (v[j]>=v[i])) min=v[j];
if (min<=v[i]) break;
}
x[i]=max+1;
}
if (l[i]==-1)
{
if (sol==-1)
sol=i;
if (x[i]<x[sol]) sol=i; else
if ((x[i]==x[sol]) && (v[i]<v[sol]))
sol=i;
}
l[i]=ord;
}
if ((sol==-1) || (x[sol]>x[n])) sol=n; else
if ((x[sol]==x[n]) && (v[sol]>v[n])) sol=n;
printf("%d\n",x[sol]);
do
{
printf("%d ",sol);
sol=l[sol];
}
while (sol>0);
return 0;}