Cod sursa(job #953807)
#include <fstream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int N;
int A[5002], D[5002], T[5002];
int ST[5002];
int result = INF, where;
int main()
{
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> A[i];
for (int i = N; i >= 1; --i)
{
D[i] = INF;
ST[0] = 0;
for (int j = i + 1; j <= N; ++j)
if (A[i] <= A[j])
{
while (ST[0] != 0 && A[ST[ST[0]]] > A[j])
--ST[0];
ST[++ST[0]] = j;
if (ST[0] == 1 && (D[ST[1]] + 1 < D[i] || (D[ST[1]] + 1 == D[i] && A[ST[1]] < A[T[i]])))
{
D[i] = D[ST[1]] + 1;
T[i] = ST[1];
}
}
if (D[i] == INF) D[i] = 1;
}
int minnow = -INF;
for (int i = 1; i <= N; ++i)
{
if (minnow == -INF || A[minnow] > A[i])
minnow = i;
if (minnow == i && result > D[i])
{
result = D[i];
where = i;
}
}
fout << result << '\n';
while (where != 0)
{
fout << where << ' ';
where = T[where];
}
fout << '\n';
fin.close();
fout.close();
}