There are n beautiful skyscrapers in New York, the height of the i-th one is h_i. Today some villains have set on fire first n - 1 of them, and now the only safety building is n-th skyscraper.

Let's call a jump from i-th skyscraper to j-th (i < j) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if i < j and one of the following conditions satisfied: 

  * i + 1 = j 
  * max(h_{i + 1}, …, h_{j - 1}) < min(h_i, h_j) 
  * max(h_i, h_j) < min(h_{i + 1}, …, h_{j - 1}). 



At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach n-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.

Input

The first line contains a single integer n (2 ≤ n ≤ 3 ⋅ 10^5) — total amount of skyscrapers.

The second line contains n integers h_1, h_2, …, h_n (1 ≤ h_i ≤ 10^9) — heights of skyscrapers.

Output

Print single number k — minimal amount of discrete jumps. We can show that an answer always exists.

Examples

Input


5
1 3 1 4 5


Output


3

Input


4
4 2 2 4


Output


1

Input


2
1 1


Output


1

Input


5
100 1 100 1 100


Output


2

Note

In the first testcase, Vasya can jump in the following way: 1 → 2 → 4 → 5.

In the second and third testcases, we can reach last skyscraper in one jump.

Sequence of jumps in the fourth testcase: 1 → 3 → 5.
import java.io.*;
import java.util.*;

public class Solution {

    private static boolean useInFile = false;
    private static boolean useOutFile = false;

    public static void main(String args[]) throws IOException {
        InOut inout = new InOut();
        Resolver resolver = new Resolver(inout);
        resolver.solve();
        inout.flush();
    }

    private static class Resolver {

        final long LONG_INF = (long) 1e18;
        final int INF = (int) (1e9 + 7);
        final int MOD = 998244353;
        long f[], inv[];
        InOut inout;

        Resolver(InOut inout) {
            this.inout = inout;
        }

        void initF(int n, int mod) {
            f = new long[n + 1];
            f[1] = 1;
            for (int i = 2; i <= n; i++) {
                f[i] = (f[i - 1] * i) % mod;
            }
        }

        void initInv(int n, int mod) {
            inv = new long[n + 1];
            inv[n] = pow(f[n], INF - 2, INF);
            for (int i = inv.length - 2; i >= 0; i--) {
                inv[i] = inv[i + 1] * (i + 1) % mod;
            }
        }

        long cmn(int n, int m, int mod) {
            return f[n] * inv[m] % mod * inv[n - m] % mod;
        }

        int d[] = {0, -1, 0, 1, 0};

        boolean legal(int r, int c, int n, int m) {
            return r >= 0 && r < n && c >= 0 && c < m;
        }

        void solve() throws IOException {
            int tt = 1;
            boolean hvt = false;
            if (hvt) {
                tt = nextInt();
//                tt = Integer.parseInt(nextLine());
            }

            for (int cs = 1; cs <= tt; cs++) {
                long rs = 0;
                int n = nextInt();
                int a[] = anInt(1, n);
                int dp[] = new int[n + 1];
                Stack<Integer> down = new Stack<>();
                Stack<Integer> up = new Stack<>();
                down.push(1);
                up.push(1);
                Arrays.fill(dp, n);
                dp[1] = 0;
                for (int i = 2; i <= n; i++) {
                    dp[i] = dp[i - 1] + 1;
                    int pre = 0;
                    boolean equal = false;
                    while (!down.isEmpty() && a[down.peek()] <= a[i]) {
                        pre = down.pop();
                        if (!equal) {
                            dp[i] = Math.min(dp[i], dp[pre] + 1);
                        }
                        if (a[pre] == a[i]) {
                            equal = true;
                        }
                    }
                    if (!down.isEmpty()) {
                        pre = down.peek();
                        if (!equal) {
                            dp[i] = Math.min(dp[i], dp[pre] + 1);
                        }
                    }
                    down.push(i);
                    equal = false;
                    while (!up.isEmpty() && a[up.peek()] >= a[i]) {
                        pre = up.pop();
                        if (!equal) {
                            dp[i] = Math.min(dp[i], dp[pre] + 1);
                        }
                        if (a[pre] == a[i]) {
                            equal = true;
                        }
                    }
                    if (!up.isEmpty()) {
                        pre = up.peek();
                        if (!equal) {
                            dp[i] = Math.min(dp[i], dp[pre] + 1);
                        }
                    }
                    up.push(i);
                }
                rs = dp[n];


                format("%d", rs);
//                format("Case #%d: %d", cs, rs);

                if (cs < tt) {
//                    format("\n");
                }
//                flush();
            }
        }

        private void updateSegTree(int n, long l, SegmentTree lft) {
            long lazy;
            lazy = 1;
            for (int j = 1; j <= l; j++) {
                lazy = (lazy + cmn((int) l, j, INF)) % INF;
                lft.modify(1, j, j, lazy);
            }
            lft.modify(1, (int) (l + 1), n, lazy);
        }

        String next() throws IOException {
            return inout.next();
        }

        String next(int n) throws IOException {
            return inout.next(n);
        }

        String nextLine() throws IOException {
            return inout.nextLine();
        }

        int nextInt() throws IOException {
            return inout.nextInt();
        }

        long nextLong(int n) throws IOException {
            return inout.nextLong(n);
        }

        int[] anInt(int i, int j) throws IOException {
            int a[] = new int[j + 1];
            for (int k = i; k <= j; k++) {
                a[k] = nextInt();
            }
            return a;
        }

        long[] anLong(int i, int j, int len) throws IOException {
            long a[] = new long[j + 1];
            for (int k = i; k <= j; k++) {
                a[k] = nextLong(len);
            }
            return a;
        }

        void print(String s, boolean nextLine) {
            inout.print(s, nextLine);
        }

        void format(String format, Object... obj) {
            inout.format(format, obj);
        }

        void flush() {
            inout.flush();
        }

        void swap(long a[], int i, int j) {
            a[i] ^= a[j];
            a[j] ^= a[i];
            a[i] ^= a[j];
        }

        int getP(int x, int p[]) {
            if (p[x] == 0 || p[x] == x) {
                return x;
            }
            return p[x] = getP(p[x], p);
        }

        void union(int x, int y, int p[]) {
            if (x < y) {
                p[y] = x;
            } else {
                p[x] = y;
            }
        }

        boolean topSort() {
            int n = adj2.length - 1;
            int d[] = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < adj2[i].size(); j++) {
                    d[adj2[i].get(j)[0]]++;
                }
            }
            List<Integer> list = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                if (d[i] == 0) {
                    list.add(i);
                }
            }
            for (int i = 0; i < list.size(); i++) {
                for (int j = 0; j < adj2[list.get(i)].size(); j++) {
                    int t = adj2[list.get(i)].get(j)[0];
                    d[t]--;
                    if (d[t] == 0) {
                        list.add(t);
                    }
                }
            }
            return list.size() == n;
        }

        class SegmentTreeNode {
            long defaultVal = 0;
            int l, r;
            long val = defaultVal, lazy = defaultVal;

            SegmentTreeNode(int l, int r) {
                this.l = l;
                this.r = r;
            }
        }

        class SegmentTree {
            SegmentTreeNode tree[];
            long defaultVal = 0;
            long inf = Long.MIN_VALUE;
            long mod = INF;
            int type = 0;
            int MODIFY_VAL = 1;
            int MODIFY_LAZY = 2;
            int MODIFY_ALL = 3;

            SegmentTree(int n) {
                this(n, 0);
            }

            SegmentTree(int n, int type) {
                this.type = type;
                assert n > 0;
                tree = new SegmentTreeNode[n << 2];
            }

            SegmentTree build(int k, int l, int r) {
                if (l > r) {
                    return this;
                }
                if (null == tree[k]) {
                    tree[k] = new SegmentTreeNode(l, r);
                }
                if (l == r) {
                    return this;
                }
                int mid = (l + r) >> 1;
                build(k << 1, l, mid);
                build(k << 1 | 1, mid + 1, r);
                return this;
            }

            void pushDown(int k) {
                if (tree[k].l == tree[k].r) {
                    return;
                }
                long lazy = tree[k].lazy;
                modify(tree[k << 1], MODIFY_ALL, lazy);
                modify(tree[k << 1 | 1], MODIFY_ALL, lazy);
                tree[k].lazy = defaultVal;
            }

            void modify(int k, int l, int r, long val) {
                if (l > r) {
                    return;
                }
                if (tree[k].l >= l && tree[k].r <= r) {
                    modify(tree[k], MODIFY_ALL, val);
                    return;
                }
                int mid = (tree[k].l + tree[k].r) >> 1;
                if (mid >= l) {
                    modify(k << 1, l, r, val);
                }
                if (mid + 1 <= r) {
                    modify(k << 1 | 1, l, r, val);
                }
                tree[k].val = Math.max(tree[k << 1].val, tree[k << 1 | 1].val);
            }

            long query(int k, int l, int r) {
                if (tree[k].l > r || tree[k].r < l) {
                    return inf;
                }
                if (tree[k].lazy != defaultVal) {
                    pushDown(k);
                }
                if (tree[k].l >= l && tree[k].r <= r) {
                    return tree[k].val;
                }
                long ans = Math.max(query(k << 1, l, r), query(k << 1 | 1, l, r));
                if (tree[k].l < tree[k].r) {
                    tree[k].val = Math.max(tree[k << 1].val, tree[k << 1 | 1].val);
                }
                return ans;
            }

            private void modify(SegmentTreeNode node, int x, long val) {
                switch (type) {
                    case 0:
                        if (x == MODIFY_VAL) {
                            node.val += val;
                        } else if (x == MODIFY_LAZY) {
                            node.lazy += val;
                        } else {
                            node.val += val;
                            node.lazy += val;
                        }
                        break;
                    case 1:
                        if (x == MODIFY_VAL) {
                            node.val = node.val * val % mod;
                        } else if (x == MODIFY_LAZY) {
                            node.lazy = node.lazy * val % mod;
                        } else {
                            node.val = node.val * val % mod;
                            node.lazy = node.lazy * val % mod;
                        }
                        break;
                }
            }
        }

        class BinaryIndexedTree {

            int n = 1;
            long C[];

            BinaryIndexedTree(int sz) {
                while (n <= sz) {
                    n <<= 1;
                }
                C = new long[n];
            }

            int lowbit(int x) {
                return x & -x;
            }

            void add(int x, long val) {
                while (x < n) {
                    C[x] += val;
                    x += lowbit(x);
                }
            }

            long getSum(int x) {
                long res = 0;
                while (x > 0) {
                    res += C[x];
                    x -= lowbit(x);
                }
                return res;
            }

            int binSearch(long sum) {
                if (sum == 0) {
                    return 0;
                }
                int n = C.length;
                int mx = 1;
                while (mx < n) {
                    mx <<= 1;
                }
                int res = 0;
                for (int i = mx / 2; i >= 1; i >>= 1) {
                    if (C[res + i] < sum) {
                        sum -= C[res + i];
                        res += i;
                    }
                }
                return res + 1;
            }
        }

        int mnS;
        int mxS;
        Map<Integer, TrieNode> SS = new HashMap<>();

        class TrieNode {
            int cnt = 0;
            boolean isMin = false;
            boolean isMax = false;
            int mnIdx = 26;
            int mxIdx = -1;

            TrieNode next[];

            TrieNode() {
                next = new TrieNode[26];
            }

            private void insert(TrieNode trie, char ch[], int i, int j) {
                while (i < ch.length) {
                    int idx = ch[i] - 'a';
                    if (null == trie.next[idx]) {
                        trie.next[idx] = new TrieNode();
                    }
                    trie.cnt++;
                    int lastMnIdx = trie.mnIdx;
                    int lastMxIdx = trie.mxIdx;
                    trie.mnIdx = Math.min(trie.mnIdx, idx);
                    trie.mxIdx = Math.max(trie.mxIdx, idx);
                    if (trie.isMin && lastMnIdx != trie.mnIdx) {
                        if (lastMnIdx != 26) {
                            notMin(trie.next[lastMnIdx]);
                        }
                        trie.next[trie.mnIdx].isMin = true;
                    }
                    if (trie.isMax && lastMxIdx != trie.mxIdx) {
                        if (lastMxIdx >= 0) {
                            notMax(trie.next[lastMxIdx]);
                        }
                        trie.next[trie.mxIdx].isMax = true;
                    }
                    trie = trie.next[idx];
                    i++;
                }
                SS.put(j + 1, trie);
                if (trie.cnt == 0) {
                    if (trie.isMin) {
                        mnS = j + 1;
                    }
                    if (trie.isMax) {
                        mxS = j + 1;
                    }
                }
            }

            private void notMin(TrieNode trie) {
                while (null != trie) {
                    trie.isMin = false;
                    int val = trie.mnIdx;
                    if (val >= 26 || val < 0 || null == trie.next[val]) {
                        break;
                    }
                    trie = trie.next[val];
                }
            }

            private void notMax(TrieNode trie) {
                while (null != trie) {
                    trie.isMax = false;
                    int val = trie.mxIdx;
                    if (val >= 26 || val < 0 || null == trie.next[val]) {
                        break;
                    }
                    trie = trie.next[val];
                }
            }
        }

        //Binary tree
        class TreeNode {
            int val;
            int tier = -1;
            TreeNode parent;
            TreeNode left;
            TreeNode right;

            TreeNode(int val) {
                this.val = val;
            }
        }

        //binary tree dfs
        void tierTree(TreeNode root) {
            if (null == root) {
                return;
            }
            if (null != root.parent) {
                root.tier = root.parent.tier + 1;
            } else {
                root.tier = 0;
            }
            tierTree(root.left);
            tierTree(root.right);
        }

        //LCA start
        TreeNode[][] lca;
        TreeNode[] tree;

        void lcaDfsTree(TreeNode root) {
            if (null == root) {
                return;
            }
            tree[root.val] = root;
            TreeNode nxt = root.parent;
            int idx = 0;
            while (null != nxt) {
                lca[root.val][idx] = nxt;
                nxt = lca[nxt.val][idx];
                idx++;
            }
            lcaDfsTree(root.left);
            lcaDfsTree(root.right);
        }

        TreeNode lcaTree(TreeNode root, int n, TreeNode x, TreeNode y) throws IOException {
            if (null == root) {
                return null;
            }
            if (-1 == root.tier) {
                tree = new TreeNode[n + 1];
                tierTree(root);
            }
            if (null == lca) {
                lca = new TreeNode[n + 1][31];
                lcaDfsTree(root);
            }
            int z = Math.abs(x.tier - y.tier);
            int xx = x.tier > y.tier ? x.val : y.val;
            while (z > 0) {
                final int zz = z;
                int l = (int) BinSearch.bs(0, 31
                        , k -> zz < (1 << k));
                xx = lca[xx][l].val;
                z -= 1 << l;
            }
            int yy = y.val;
            if (x.tier <= y.tier) {
                yy = x.val;
            }
            while (xx != yy) {
                final int xxx = xx;
                final int yyy = yy;
                int l = (int) BinSearch.bs(0, 31
                        , k -> (1 << k) <= tree[xxx].tier && lca[xxx][(int) k] != lca[yyy][(int) k]);
                xx = lca[xx][l].val;
                yy = lca[yy][l].val;
            }
            return tree[xx];
        }
        //LCA end

        //graph
        List<Integer> adj[];
        List<int[]> adj2[];

        void initGraph(int n, int m, boolean hasW, boolean directed, int type) throws IOException {
            if (type == 1) {
                adj = new List[n + 1];
            } else {
                adj2 = new List[n + 1];
            }
            for (int i = 1; i <= n; i++) {
                if (type == 1) {
                    adj[i] = new ArrayList<>();
                } else {
                    adj2[i] = new ArrayList<>();
                }
            }
            for (int i = 0; i < m; i++) {
                int f = nextInt();
                int t = nextInt();
                if (type == 1) {
                    adj[f].add(t);
                    if (!directed) {
                        adj[t].add(f);
                    }
                } else {
                    int w = hasW ? nextInt() : 0;
                    adj2[f].add(new int[]{t, w});
                    if (!directed) {
                        adj2[t].add(new int[]{f, w});
                    }
                }
            }
        }

        void getDiv(Map<Integer, Integer> map, int n) {
            int sqrt = (int) Math.sqrt(n);
            for (int i = 2; i <= sqrt; i++) {
                int cnt = 0;
                while (n % i == 0) {
                    cnt++;
                    n /= i;
                }
                if (cnt > 0) {
                    map.put(i, cnt);
                }
            }
            if (n > 1) {
                map.put(n, 1);
            }
        }

        boolean[] generatePrime(int n) {
            boolean p[] = new boolean[n + 1];
            p[2] = true;

            for (int i = 3; i <= n; i += 2) {
                p[i] = true;
            }

            for (int i = 3; i <= Math.sqrt(n); i += 2) {
                if (!p[i]) {
                    continue;
                }
                for (int j = i * i; j <= n; j += i << 1) {
                    p[j] = false;
                }
            }
            return p;
        }

        boolean isPrime(long n) { //determines if n is a prime number
            int p[] = {2, 3, 5, 233, 331};
            int pn = p.length;
            long s = 0, t = n - 1;//n - 1 = 2^s * t
            while ((t & 1) == 0) {
                t >>= 1;
                ++s;
            }
            for (int i = 0; i < pn; ++i) {
                if (n == p[i]) {
                    return true;
                }
                long pt = pow(p[i], t, n);
                for (int j = 0; j < s; ++j) {
                    long cur = llMod(pt, pt, n);
                    if (cur == 1 && pt != 1 && pt != n - 1) {
                        return false;
                    }
                    pt = cur;
                }
                if (pt != 1) {
                    return false;
                }
            }
            return true;
        }

        long llMod(long a, long b, long mod) {
            return (a * b - (long) ((double) a / mod * b + 0.5) * mod + mod) % mod;
//        long r = 0;
//        a %= mod;
//        b %= mod;
//        while (b > 0) {
//            if ((b & 1) == 1) {
//                r = (r + a) % mod;
//            }
//            b >>= 1;
//            a = (a << 1) % mod;
//        }
//        return r;
        }

        long pow(long a, long n) {
            long ans = 1;
            while (n > 0) {
                if ((n & 1) == 1) {
                    ans = ans * a;
                }
                a = a * a;
                n >>= 1;
            }
            return ans;
        }

        long pow(long a, long n, long mod) {
            long ans = 1;
            while (n > 0) {
                if ((n & 1) == 1) {
                    ans = llMod(ans, a, mod);
                }
                a = llMod(a, a, mod);
                n >>= 1;
            }
            return ans;
        }

        private long[][] initC(int n) {
            long c[][] = new long[n][n];

            for (int i = 0; i < n; i++) {
                c[i][0] = 1;
            }

            for (int i = 1; i < n; i++) {
                for (int j = 1; j <= i; j++) {
                    c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                }
            }
            return c;
        }

        /**
         * ps: n >= m, choose m from n;
         */
//        private int cmn(long n, long m) {
//            if (m > n) {
//                n ^= m;
//                m ^= n;
//                n ^= m;
//            }
//            m = Math.min(m, n - m);
//
//            long top = 1;
//            long bot = 1;
//            for (long i = n - m + 1; i <= n; i++) {
//                top = (top * i) % MOD;
//            }
//            for (int i = 1; i <= m; i++) {
//                bot = (bot * i) % MOD;
//            }
//
//            return (int) ((top * pow(bot, MOD - 2, MOD)) % MOD);
//        }

        long gcd(long a, long b) {
            if (a < b) {
                return gcd(b, a);
            }
            while (b != 0) {
                long tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }

        int[] unique(int a[], Map<Integer, Integer> idx, Map<Integer, Integer> cnt) {
            Integer order[] = new Integer[a.length];
            for (int i = 0; i < a.length; i++) {
                order[i] = i;
            }
            Arrays.sort(order, Comparator.comparingInt(o -> a[o]));
            int tmp[] = new int[a.length];
            for (int i = 0; i < a.length; i++) {
                tmp[i] = a[order[i]];
            }
            int j = 0;
            for (int i = 0; i < tmp.length; i++) {
                if (i == 0 || tmp[i] > tmp[i - 1]) {
                    idx.put(tmp[i], j++);
                }
                cnt.put(idx.get(tmp[i]), cnt.getOrDefault(idx.get(tmp[i]), 0) + 1);
            }
            int rs[] = new int[j];
            j = 0;
            for (int key : idx.keySet()) {
                rs[j++] = key;
            }
            Arrays.sort(rs);
            return rs;
        }

        boolean isEven(long n) {
            return (n & 1) == 0;
        }

        static class BinSearch {

            static long bs(long l, long r, IBinSearch sort) throws IOException {
                while (l < r) {
                    long m = l + (r - l) / 2;
                    if (sort.binSearchCmp(m)) {
                        l = m + 1;
                    } else {
                        r = m;
                    }
                }
                return l;
            }

            interface IBinSearch {
                boolean binSearchCmp(long k) throws IOException;
            }

        }
    }

    private static class InOut {
        private BufferedReader br;
        private StreamTokenizer st;
        private PrintWriter pw;

        InOut() throws FileNotFoundException {
            if (useInFile) {
                System.setIn(new FileInputStream("resources/inout/in.text"));
            }
            if (useOutFile) {
                System.setOut(new PrintStream("resources/inout/out.text"));
            }
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StreamTokenizer(br);
            pw = new PrintWriter(new OutputStreamWriter(System.out));
            st.ordinaryChar('\'');
            st.ordinaryChar('\"');
            st.ordinaryChar('/');
        }

        private long[] anLong(int n) throws IOException {
            long a[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        private String next() throws IOException {
            st.nextToken();
            return st.sval;
        }

        private String next(int len) throws IOException {
            char ch[] = new char[len];
            int cur = 0;
            char c;
            while ((c = (char) br.read()) == '\n' || c == '\r' || c == ' ' || c == '\t') ;
            do {
                ch[cur++] = c;
            } while (!((c = (char) br.read()) == '\n' || c == '\r' || c == ' ' || c == '\t'));
            return String.valueOf(ch, 0, cur);
        }

        private int nextInt() throws IOException {
            st.nextToken();
            return (int) st.nval;
        }

        private long nextLong(int n) throws IOException {
            return Long.parseLong(next(n));
        }

        private double nextDouble() throws IOException {
            st.nextToken();
            return st.nval;
        }

        private String[] nextSS(String reg) throws IOException {
            return br.readLine().split(reg);
        }

        private String nextLine() throws IOException {
            return br.readLine();
        }

        private void print(String s, boolean newLine) {
            if (null != s) {
                pw.print(s);
            }
            if (newLine) {
                pw.println();
            }
        }

        private void format(String format, Object... obj) {
            pw.format(format, obj);
        }

        private void flush() {
            pw.flush();
        }
    }

    private static class FFT {
        double[] roots;
        int maxN;

        public FFT(int maxN) {
            this.maxN = maxN;
            initRoots();
        }

        public long[] multiply(int[] a, int[] b) {
            int minSize = a.length + b.length - 1;
            int bits = 1;
            while (1 << bits < minSize) bits++;
            int N = 1 << bits;
            double[] aa = toComplex(a, N);
            double[] bb = toComplex(b, N);
            fftIterative(aa, false);
            fftIterative(bb, false);
            double[] c = new double[aa.length];
            for (int i = 0; i < N; i++) {
                c[2 * i] = aa[2 * i] * bb[2 * i] - aa[2 * i + 1] * bb[2 * i + 1];
                c[2 * i + 1] = aa[2 * i] * bb[2 * i + 1] + aa[2 * i + 1] * bb[2 * i];
            }
            fftIterative(c, true);
            long[] ret = new long[minSize];
            for (int i = 0; i < ret.length; i++) {
                ret[i] = Math.round(c[2 * i]);
            }
            return ret;
        }

        static double[] toComplex(int[] arr, int size) {
            double[] ret = new double[size * 2];
            for (int i = 0; i < arr.length; i++) {
                ret[2 * i] = arr[i];
            }
            return ret;
        }

        void initRoots() {
            roots = new double[2 * (maxN + 1)];
            double ang = 2 * Math.PI / maxN;
            for (int i = 0; i <= maxN; i++) {
                roots[2 * i] = Math.cos(i * ang);
                roots[2 * i + 1] = Math.sin(i * ang);
            }
        }

        int bits(int N) {
            int ret = 0;
            while (1 << ret < N) ret++;
            if (1 << ret != N) throw new RuntimeException();
            return ret;
        }

        void fftIterative(double[] array, boolean inv) {
            int bits = bits(array.length / 2);
            int N = 1 << bits;
            for (int from = 0; from < N; from++) {
                int to = Integer.reverse(from) >>> (32 - bits);
                if (from < to) {
                    double tmpR = array[2 * from];
                    double tmpI = array[2 * from + 1];
                    array[2 * from] = array[2 * to];
                    array[2 * from + 1] = array[2 * to + 1];
                    array[2 * to] = tmpR;
                    array[2 * to + 1] = tmpI;
                }
            }
            for (int n = 2; n <= N; n *= 2) {
                int delta = 2 * maxN / n;
                for (int from = 0; from < N; from += n) {
                    int rootIdx = inv ? 2 * maxN : 0;
                    double tmpR, tmpI;
                    for (int arrIdx = 2 * from; arrIdx < 2 * from + n; arrIdx += 2) {
                        tmpR = array[arrIdx + n] * roots[rootIdx] - array[arrIdx + n + 1] * roots[rootIdx + 1];
                        tmpI = array[arrIdx + n] * roots[rootIdx + 1] + array[arrIdx + n + 1] * roots[rootIdx];
                        array[arrIdx + n] = array[arrIdx] - tmpR;
                        array[arrIdx + n + 1] = array[arrIdx + 1] - tmpI;
                        array[arrIdx] += tmpR;
                        array[arrIdx + 1] += tmpI;
                        rootIdx += (inv ? -delta : delta);
                    }
                }
            }
            if (inv) {
                for (int i = 0; i < array.length; i++) {
                    array[i] /= N;
                }
            }
        }
    }
}