The life goes up and down, just like nice sequences. Sequence t1, t2, ..., tn is called nice if the following two conditions are satisfied: 

  * ti < ti + 1 for each odd i < n; 
  * ti > ti + 1 for each even i < n. 



For example, sequences (2, 8), (1, 5, 1) and (2, 5, 1, 100, 99, 120) are nice, while (1, 1), (1, 2, 3) and (2, 5, 3, 2) are not.

Bear Limak has a sequence of positive integers t1, t2, ..., tn. This sequence is not nice now and Limak wants to fix it by a single swap. He is going to choose two indices i < j and swap elements ti and tj in order to get a nice sequence. Count the number of ways to do so. Two ways are considered different if indices of elements chosen for a swap are different.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 150 000) — the length of the sequence.

The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 150 000) — the initial sequence. It's guaranteed that the given sequence is not nice.

Output

Print the number of ways to swap two elements exactly once in order to get a nice sequence.

Examples

Input

5
2 8 4 7 7


Output

2


Input

4
200 150 100 50


Output

1


Input

10
3 2 1 4 1 4 1 4 1 4


Output

8


Input

9
1 2 3 4 5 6 7 8 9


Output

0

Note

In the first sample, there are two ways to get a nice sequence with one swap: 

  1. Swap t2 = 8 with t4 = 7. 
  2. Swap t1 = 2 with t5 = 7. 



In the second sample, there is only one way — Limak should swap t1 = 200 with t4 = 50.

//package india;


import java.io.*;
import java.util.*;

public class C {

    public static void main(String[] args) {
        CIO io = new CIO();
        try {
            Csolver solver = new Csolver(io);
        } finally {
            io.close();
        }
    }

}

class Csolver {
    
    int n;
    int[] t;
    int count;
    HashSet<Swap> viableSwaps;
    boolean[] tried;

    public Csolver(CIO io) {
        n = io.nextInt();
        t = new int[n];
        for (int i=0; i<n; i++) {
            t[i] = io.nextInt();
        }
        tried = new boolean[n];
        
        List<Integer> streaks = new ArrayList<>();
        for (int i=1; i<n; i++) {
            if (i%2 == 0 && t[i] >= t[i-1]) {
                int bah = Math.max(0, i-1);
                streaks.add(bah);
            } else if (i%2 != 0 && t[i] <= t[i-1]) {
                int bah = Math.max(0, i-1);
                streaks.add(bah);
            }
            if (streaks.size() > 8) {
                io.println("0");
                return;
            }
        }
        viableSwaps = new HashSet<>();
        for (int i=streaks.size()-1; i>=1; i--) {
            int a = streaks.get(i);
            int b = streaks.get(i-1);
            if (b-a > 1) continue;
            if ((t[a+1] > t[a] && t[a] > t[a-1])
                || (t[a+1] < t[a] && t[a] < t[a-1])) {
                    //streaks.remove(i);
            }
        }
        for (int s : streaks) {
            doShit(s, streaks);
        }
        //doShit(streaks.get(0), streaks.get(1));
        //doShit(streaks.get(1), streaks.get(0));
        io.println(viableSwaps.size());
    }
    
    void doShit(int start, List<Integer> others) {
        start = Math.max(0, start-2);
        for (int i=start; i<n && i<=start+8; i++) {
            if (tried[i]) continue;
            tried[i] = true;
            for (int j=0; j<n; j++) {
                swap(i,j);
                boolean allOk = verifyNicenessAround(i, j);
                for (int other : others) {
                    if (!verifyNicenessAround(other)) allOk = false;
                    if (!allOk) break;
                }
                if (allOk) addViableSwap(i,j);
                swap(i,j);
            }
        }
    }
    
    void swap(int i, int j) {
        int helper = t[i];
        t[i] = t[j];
        t[j] = helper;
    }
    
    boolean verifyNicenessAround(int i, int j) {
        return (verifyNicenessAround(i) && verifyNicenessAround(j));
    }
    
    boolean verifyNicenessAround(int a) {
        int startRange = Math.max(0, a-4);
        int endRange = Math.min(n-1, startRange+10);
        for (int i=startRange+1; i<=endRange; i++) {
            if (i%2 == 0 && t[i] >= t[i-1]) {
                return false;
            } else if (i%2 != 0 && t[i] <= t[i-1]) {
                return false;
            }
        }
        return true;
    }
    
    void addViableSwap(int i, int j) {
        viableSwaps.add(new Swap(i,j));
    }
    
}

class Swap {
    int i;
    int j;

    public Swap(int i, int j) {
        this.i = Math.min(i,j);
        this.j = Math.max(i,j);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj.getClass() != this.getClass()) return false;
        Swap other = (Swap) obj;
        if (other.i != this.i) return false;
        if (other.j != this.j) return false;
        return true;
    }

    @Override
    public int hashCode() {
        return i*10000008+j;
    }
    
}


class CIO extends PrintWriter {
    private InputStreamReader r;
    private static final int BUFSIZE = 1 << 15;
    private char[] buf;
    private int bufc;
    private int bufi;
    private StringBuilder sb;

    public CIO() {
            super(new BufferedOutputStream(System.out));
            r = new InputStreamReader(System.in);

            buf = new char[BUFSIZE];
            bufc = 0;
            bufi = 0;
            sb = new StringBuilder();
    }

    private void fillBuf() throws IOException {
            bufi = 0;
            bufc = 0;
            while(bufc == 0) {
                    bufc = r.read(buf, 0, BUFSIZE);
                    if(bufc == -1) {
                            bufc = 0;
                            return;
                    }
            }
    }

    private boolean pumpBuf() throws IOException {
            if(bufi == bufc) {
                    fillBuf();
            }
            return bufc != 0;
    }

    private boolean isDelimiter(char c) {
            return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f';
    }

    private void eatDelimiters() throws IOException {
            while(true) {
                    if(bufi == bufc) {
                            fillBuf();
                            if(bufc == 0) throw new RuntimeException("IO: Out of input.");
                    }

                    if(!isDelimiter(buf[bufi])) break;
                    ++bufi;
            }
    }

    public String next() {
            try {
                    sb.setLength(0);

                    eatDelimiters();
                    int start = bufi;

                    while(true) {
                            if(bufi == bufc) {
                                    sb.append(buf, start, bufi - start);
                                    fillBuf();
                                    start = 0;
                                    if(bufc == 0) break;
                            }

                            if(isDelimiter(buf[bufi])) break;
                            ++bufi;
                    }

                    sb.append(buf, start, bufi - start);

                    return sb.toString();
            } catch(IOException e) {
                    throw new RuntimeException("IO.next: Caught IOException.");
            }
    }

    public int nextInt() {
            try {
                    int ret = 0;

                    eatDelimiters();

                    boolean positive = true;
                    if(buf[bufi] == '-') {
                            ++bufi;
                            if(!pumpBuf()) throw new RuntimeException("IO.nextInt: Invalid int.");
                            positive = false;
                    }

                    boolean first = true;
                    while(true) {
                            if(!pumpBuf()) break;
                            if(isDelimiter(buf[bufi])) {
                                    if(first) throw new RuntimeException("IO.nextInt: Invalid int.");
                                    break;
                            }
                            first = false;

                            if(buf[bufi] >= '0' && buf[bufi] <= '9') {
                                    if(ret < -214748364) throw new RuntimeException("IO.nextInt: Invalid int.");
                                    ret *= 10;
                                    ret -= (int)(buf[bufi] - '0');
                                    if(ret > 0) throw new RuntimeException("IO.nextInt: Invalid int.");
                            } else {
                                    throw new RuntimeException("IO.nextInt: Invalid int.");
                            }

                            ++bufi;
                    }

                    if(positive) {
                            if(ret == -2147483648) throw new RuntimeException("IO.nextInt: Invalid int.");
                            ret = -ret;
                    }

                    return ret;
            } catch(IOException e) {
                    throw new RuntimeException("IO.nextInt: Caught IOException.");
            }
    }

    public long nextLong() {
            try {
                    long ret = 0;

                    eatDelimiters();

                    boolean positive = true;
                    if(buf[bufi] == '-') {
                            ++bufi;
                            if(!pumpBuf()) throw new RuntimeException("IO.nextLong: Invalid long.");
                            positive = false;
                    }

                    boolean first = true;
                    while(true) {
                            if(!pumpBuf()) break;
                            if(isDelimiter(buf[bufi])) {
                                    if(first) throw new RuntimeException("IO.nextLong: Invalid long.");
                                    break;
                            }
                            first = false;

                            if(buf[bufi] >= '0' && buf[bufi] <= '9') {
                                    if(ret < -922337203685477580L) throw new RuntimeException("IO.nextLong: Invalid long.");
                                    ret *= 10;
                                    ret -= (long)(buf[bufi] - '0');
                                    if(ret > 0) throw new RuntimeException("IO.nextLong: Invalid long.");
                            } else {
                                    throw new RuntimeException("IO.nextLong: Invalid long.");
                            }

                            ++bufi;
                    }

                    if(positive) {
                            if(ret == -9223372036854775808L) throw new RuntimeException("IO.nextLong: Invalid long.");
                            ret = -ret;
                    }

                    return ret;
            } catch(IOException e) {
                    throw new RuntimeException("IO.nextLong: Caught IOException.");
            }
    }

    public double nextDouble() {
            return Double.parseDouble(next());
    }

}