Pagini recente » Cod sursa (job #1465493) | Cod sursa (job #1288054) | Cod sursa (job #3262137) | Cod sursa (job #2834016) | Cod sursa (job #2863263)
/*
__
/\ \
_ __ ___ ___\ \ \/'\ ___ __ ___ ___ __
/\`'__\/ __`\ /'___\ \ , < / __`\ /'__`\ /' _ `\ /' _ `\ /'__`\
\ \ \//\ \L\ \/\ \__/\ \ \\`\ /\ \L\ \/\ \L\.\_/\ \/\ \/\ \/\ \/\ \L\.\_
\ \_\\ \____/\ \____\\ \_\ \_\ \____/\ \__/.\_\ \_\ \_\ \_\ \_\ \__/.\_\
\/_/ \/___/ \/____/ \/_/\/_/\/___/ \/__/\/_/\/_/\/_/\/_/\/_/\/__/\/_/
*/
#ifndef __AHA__HEADER
#define __AHA__HEADER
#include <bits/stdc++.h>
using namespace std;
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define ft first
#define sd second
#define sz(x) (i6) x.size()
#define psb(x) push_back(x)
#define ppb() pop_back()
#define bg(x) x.begin()
#define ed(x) x.end()
#define col(x) x.begin(), x.end()
#define srt(x) sort(x.begin(), x.end())
#define pq priority_queue
#define fn function
#ifdef LOCAL
#else
#define dbg(...)
#endif
#define endl '\n'
template <typename T>
using vec = vector<T>;
template <typename T>
using deq = deque<T>;
template <typename K, typename V>
using hmap = unordered_map<K, V>;
using str = string;
using vb = vec<bool>;
using byte = int8_t;
using i3 = int32_t;
using i6 = int64_t;
using i64 = int64_t;
using u3 = uint32_t;
using u6 = uint64_t;
using d6 = long double;
using p3 = pair<i3, i3>;
using vi3 = vec<i3>;
using vp3 = vec<p3>;
using p6 = pair<i6, i6>;
using vi6 = vec<i6>;
using vd6 = vec<d6>;
using vp6 = vec<p6>;
using vv = vec<vi6>;
using dp6 = deq<p6>;
using di6 = deq<i6>;
using mi6 = map<i6, i6>;
using mp6 = map<p6, i6>;
using si6 = set<i6>;
using hi6 = hmap<i6, i6>;
using bs = bitset<64>;
using graph = vv;
using matrix = vv;
const d6 EPS = 1 / 1000000.0;
const i6 ZERO = 0;
const i6 _0 = ZERO;
const i6 ONE = 1;
const i6 _1 = ONE;
const i6 INF = INT64_MAX / 4;
const i6 NINF = -INF;
namespace std {
template <typename T1, typename T2>
struct hash<pair<T1, T2>> {
std::size_t operator()(const pair<T1, T2>& pair) const noexcept {
return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);
}
};
} // namespace std
template <typename T1, typename T2>
istream& operator>>(istream& stream, pair<T1, T2>& p) {
stream >> p.ft;
stream >> p.sd;
return stream;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
return stream << p.ft << " " << p.sd;
}
template <typename T>
istream& operator>>(istream& stream, vec<T>& v) {
if (v.empty()) {
u6 len;
stream >> len;
v.assign(len, T());
}
for (auto i = 0; i < sz(v); i++) {
stream >> v[i];
}
return stream;
}
template <typename T>
ostream& operator<<(ostream& stream, const vec<T>& v) {
if (!v.empty()) {
stream << v[0];
}
for (auto i = 1; i < sz(v); i++) {
stream << " " << v[i];
}
return stream;
}
template <typename T>
istream& operator>>(istream& stream, deq<T>& v) {
if (v.empty()) {
u6 len;
stream >> len;
v.assign(len, T());
}
for (auto i = 0; i < sz(v); i++) {
stream >> v[i];
}
return stream;
}
template <typename T>
ostream& operator<<(ostream& stream, const deq<T>& v) {
if (!v.empty()) {
stream << v[0];
}
for (auto i = 1; i < sz(v); i++) {
stream << " " << v[i];
}
return stream;
}
#endif
i64 n;
vi6 v, dp;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// #ifdef LOCAL
ifstream cin{"subsir2.in"};
ofstream cout{"subsir2.out"};
// #endif
cin >> n;
v.assign(n, 0);
dp.assign(n, INF);
for(i64 i = 0; i < n; i++){
cin >> v[i];
}
dp[n - 1] = 1;
for(i64 i = n - 2; i >= 0; i--){
i64 mi = INF;
i64 mc = INF;
for(i64 j = i + 1; j < n; j++){
if(v[j] >= v[i] && v[j] < mc){
mi = min(mi, dp[j]);
mc = v[j];
}
}
if(mi == INF){
mi = 0;
}
dp[i] = mi + 1;
}
i64 last = INF;
i64 res = INF;
i64 mi = INF;
for(i64 i = 0; i < n; i++){
if(v[i] < mi){
if(res == dp[i] && v[last] > v[i]){
last = i;
}else if(res > dp[i]){
last = i;
res = dp[i];
}
mi = v[i];
}
}
cout << res << endl;
cout << last + 1;
if(res >= 2){
cout << ' ';
}
for(i64 i = res - 1; i > 0; i--){
i64 mc = INF;
mi = INF;
i64 r = 0;
for(i64 j = last + 1; j < n; j++){
if(v[j] >= v[last] && v[j] < mc && dp[j] == i && v[j] < mi){
r = j;
mi = v[j];
mc = v[j];
}else if(v[j] >= v[last] && v[j] < mc){
mc = v[j];
}
}
last = r;
cout << last + 1;
if(i != 1){
cout << ' ';
}
}
return 0;
}