#include <bits/stdc++.h>
#pragma comment(linker, "/stack:20000000")
using namespace std;
template <typename T1, typename T2, typename T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple(){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <typename T1, typename T2, typename T3>
bool operator<(const triple<T1, T2, T3> &t1, const triple<T1, T2, T3> &t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else
    return t1.c < t2.c;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(std::ostream &os, const triple<T1, T2, T3> &tr) {
  os << "{" << tr.a << "," << tr.b << "," << tr.c << "}";
  return os;
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::set<T> &v) {
  bool first = true;
  os << "[";
  for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::map<T1, T2> &v) {
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T, typename T2>
void printarray(T a[], T2 sz, T2 beg = 0) {
  for (T2 i = beg; i < sz; i++) cout << a[i] << " ";
}
inline long long binpow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(int a, int b) { return a / gcd(a, b) * (long long)b; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
inline long long lcm(long long a, long long b, long long c) {
  return lcm(lcm(a, b), c);
}
inline long long lcm(int a, int b, int c) {
  return lcm(lcm(a, b), (long long)c);
}
inline long long max(long long a, long long b) { return (a > b) ? a : b; }
inline int max(int a, int b) { return (a > b) ? a : b; }
inline double max(double a, double b) { return (a > b) ? a : b; }
inline long long max(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline double max(double a, double b, double c) { return max(a, max(b, c)); }
inline long long min(long long a, long long b) { return (a < b) ? a : b; }
inline int min(int a, int b) { return (a < b) ? a : b; }
inline double min(double a, double b) { return (a < b) ? a : b; }
inline long long min(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
inline int min(int a, int b, int c) { return min(a, min(b, c)); }
inline double min(double a, double b, double c) { return min(a, min(b, c)); }
inline void getar(int *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", a + ii);
  }
}
inline void getar(long long *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64", a + ii);
  }
}
int a[300010];
map<int, int> fp;
map<int, int> lp;
long long pref[300010];
long long potr[300010];
long long maxs = -1000000000 * 1LL * 1000000000;
int x = 0;
int y = 1;
vector<int> ans;
int main() {
  int n;
  scanf("%d", &n);
  getar(a, n);
  for (int i = 1; i <= n; i++) {
    pref[i] = a[i - 1] + pref[i - 1];
    potr[i] = (a[i - 1] < 0 ? a[i - 1] : 0) + potr[i - 1];
  }
  for (int i = 0; i < n; i++) {
    lp[a[i]] = i;
    fp[a[n - i - 1]] = n - i - 1;
  }
  for (int i = 0; i < n; i++) {
    int val = a[i];
    int l = fp[val];
    int r = lp[val];
    if (l == r) continue;
    long long res = pref[r + 1] - pref[l];
    if (r > l + 1) {
      res -= (potr[r] - potr[l + 1]);
    }
    if (res > maxs) {
      maxs = res;
      x = l;
      y = r;
    }
  }
  for (int i = 0; i < n; i++) {
    if (i < x || i > y || i != x && i != y && a[i] < 0) ans.push_back(i);
  }
  cout << maxs << " " << ans.size() << endl;
  if (ans.size() > 0) {
    for (int i = 0; i < ans.size(); i++) {
      printf("%d ", ans[i] + 1);
    }
    cout << endl;
  }
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

— Oh my sweet Beaverette, would you fancy a walk along a wonderful woodland belt with me? 

— Of course, my Smart Beaver! Let us enjoy the splendid view together. How about Friday night? 

At this point the Smart Beaver got rushing. Everything should be perfect by Friday, so he needed to prepare the belt to the upcoming walk. He needed to cut down several trees.

Let's consider the woodland belt as a sequence of trees. Each tree i is described by the esthetic appeal ai — some trees are very esthetically pleasing, others are 'so-so', and some trees are positively ugly!

The Smart Beaver calculated that he needed the following effects to win the Beaverette's heart: 

  * The first objective is to please the Beaverette: the sum of esthetic appeal of the remaining trees must be maximum possible; 
  * the second objective is to surprise the Beaverette: the esthetic appeal of the first and the last trees in the resulting belt must be the same; 
  * and of course, the walk should be successful: there must be at least two trees in the woodland belt left. 



Now help the Smart Beaver! Which trees does he need to cut down to win the Beaverette's heart?

Input

The first line contains a single integer n — the initial number of trees in the woodland belt, 2 ≤ n. The second line contains space-separated integers ai — the esthetic appeals of each tree. All esthetic appeals do not exceed 109 in their absolute value.

  * to get 30 points, you need to solve the problem with constraints: n ≤ 100 (subproblem A1); 
  * to get 100 points, you need to solve the problem with constraints: n ≤ 3·105 (subproblems A1+A2). 

Output

In the first line print two integers — the total esthetic appeal of the woodland belt after the Smart Beaver's intervention and the number of the cut down trees k.

In the next line print k integers — the numbers of the trees the Beaver needs to cut down. Assume that the trees are numbered from 1 to n from left to right.

If there are multiple solutions, print any of them. It is guaranteed that at least two trees have equal esthetic appeal.

Examples

Input

5
1 2 3 1 2


Output

8 1
1 

Input

5
1 -2 3 1 -2


Output

5 2
2 5 

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:20000000")
using namespace std;
template <typename T1, typename T2, typename T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple(){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <typename T1, typename T2, typename T3>
bool operator<(const triple<T1, T2, T3> &t1, const triple<T1, T2, T3> &t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else
    return t1.c < t2.c;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(std::ostream &os, const triple<T1, T2, T3> &tr) {
  os << "{" << tr.a << "," << tr.b << "," << tr.c << "}";
  return os;
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::set<T> &v) {
  bool first = true;
  os << "[";
  for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::map<T1, T2> &v) {
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T, typename T2>
void printarray(T a[], T2 sz, T2 beg = 0) {
  for (T2 i = beg; i < sz; i++) cout << a[i] << " ";
}
inline long long binpow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(int a, int b) { return a / gcd(a, b) * (long long)b; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
inline long long lcm(long long a, long long b, long long c) {
  return lcm(lcm(a, b), c);
}
inline long long lcm(int a, int b, int c) {
  return lcm(lcm(a, b), (long long)c);
}
inline long long max(long long a, long long b) { return (a > b) ? a : b; }
inline int max(int a, int b) { return (a > b) ? a : b; }
inline double max(double a, double b) { return (a > b) ? a : b; }
inline long long max(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline double max(double a, double b, double c) { return max(a, max(b, c)); }
inline long long min(long long a, long long b) { return (a < b) ? a : b; }
inline int min(int a, int b) { return (a < b) ? a : b; }
inline double min(double a, double b) { return (a < b) ? a : b; }
inline long long min(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
inline int min(int a, int b, int c) { return min(a, min(b, c)); }
inline double min(double a, double b, double c) { return min(a, min(b, c)); }
inline void getar(int *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%d", a + ii);
  }
}
inline void getar(long long *a, int n) {
  for (int ii = 0; ii < n; ii++) {
    scanf("%I64", a + ii);
  }
}
int a[300010];
map<int, int> fp;
map<int, int> lp;
long long pref[300010];
long long potr[300010];
long long maxs = -1000000000 * 1LL * 1000000000;
int x = 0;
int y = 1;
vector<int> ans;
int main() {
  int n;
  scanf("%d", &n);
  getar(a, n);
  for (int i = 1; i <= n; i++) {
    pref[i] = a[i - 1] + pref[i - 1];
    potr[i] = (a[i - 1] < 0 ? a[i - 1] : 0) + potr[i - 1];
  }
  for (int i = 0; i < n; i++) {
    lp[a[i]] = i;
    fp[a[n - i - 1]] = n - i - 1;
  }
  for (int i = 0; i < n; i++) {
    int val = a[i];
    int l = fp[val];
    int r = lp[val];
    if (l == r) continue;
    long long res = pref[r + 1] - pref[l];
    if (r > l + 1) {
      res -= (potr[r] - potr[l + 1]);
    }
    if (res > maxs) {
      maxs = res;
      x = l;
      y = r;
    }
  }
  for (int i = 0; i < n; i++) {
    if (i < x || i > y || i != x && i != y && a[i] < 0) ans.push_back(i);
  }
  cout << maxs << " " << ans.size() << endl;
  if (ans.size() > 0) {
    for (int i = 0; i < ans.size(); i++) {
      printf("%d ", ans[i] + 1);
    }
    cout << endl;
  }
  return 0;
}

```