private static void check_answer(ArrayList<Integer> A) {
        for (int i = 0; i < A.size(); ++i) {
            if ((i & 1) != 0) {
                assert(A.get(i) >= A.get(i - 1));
                if (i < A.size() - 1) {
                    assert(A.get(i) >= A.get(i + 1));
                }
            } else {
                if (i > 0) {
                    assert(A.get(i - 1) >= A.get(i));
                }
                if (i < A.size() - 1) {
                    assert(A.get(i + 1) >= A.get(i));
                }
            }
        }
    }