Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.math.BigInteger;
- import java.util.*;
- public class monotone_nv_bigint {
- public static void main(String[] args) {
- new monotone_nv_bigint().run();
- }
- BufferedReader br;
- StringTokenizer in;
- PrintWriter out;
- public String nextToken() throws IOException {
- while (in == null || !in.hasMoreTokens()) {
- in = new StringTokenizer(br.readLine());
- }
- return in.nextToken();
- }
- public int nextInt() throws IOException {
- return Integer.parseInt(nextToken());
- }
- public long nextLong() throws IOException {
- return Long.parseLong(nextToken());
- }
- public double nextDouble() throws IOException {
- return Double.parseDouble(nextToken());
- }
- int a[];
- boolean check(int pos, int cnt) throws IOException {
- boolean f = true;
- for (int i = pos - cnt + 1; i < pos; i++) {
- if (a[i] < a[i + 1]) {
- f = false;
- }
- }
- if (f) {
- return true;
- }
- f = true;
- for (int i = pos - cnt + 1; i < pos; i++) {
- if (a[i] > a[i + 1]) {
- f = false;
- }
- }
- return f;
- }
- void solve() throws IOException {
- int n = nextInt();
- assert 1 <= n && n <= 50000;
- a = new int[n + 1];
- BigInteger dp[] = new BigInteger[4];
- int parent[] = new int[n + 1];
- for (int i = 0; i < n; i++) {
- a[i + 1] = nextInt();
- assert 0 <= a[i + 1] && a[i + 1] <= (int) 1e9;
- }
- dp[0] = dp[1] = BigInteger.ONE;
- dp[2] = BigInteger.valueOf(2);
- for (int i = 3; i <= n; i++) {
- dp[3] = dp[2];
- parent[i] = i - 1;
- for (int j = 2; j < 4; j++) {
- if (check(i, j)) {
- BigInteger tmp = dp[3 - j].multiply(BigInteger.valueOf(j));
- if (dp[3].compareTo(tmp) < 0) {
- dp[3] = tmp;
- parent[i] = i - j;
- }
- }
- }
- for (int j = 0; j < 3; j++) {
- dp[j] = dp[j + 1];
- }
- }
- //out.println(dp[3].toString());
- ArrayList<Integer> ans = new ArrayList<Integer>();
- int t = n;
- while (t > 0) {
- ans.add(t);
- t = parent[t];
- }
- Collections.reverse(ans);
- out.println(ans.size());
- for (int i = 0; i < ans.size(); i++) {
- out.print(ans.get(i) + ((i == ans.size() - 1) ? "\n" : " "));
- }
- }
- public void run() {
- try {
- br = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- //br = new BufferedReader(new FileReader("monotone.in"));
- //out = new PrintWriter("monotone.out");
- solve();
- out.close();
- } catch (IOException e) {
- e.printStackTrace();
- System.exit(1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement