Cho dãy số nguyên a1, a2, ..., an trong đó ai ∈ [1, n]. Hãy đếm xem có bao nhiêu cặp (i, j) thỏa mãn:

• ~ i < j ~ .

• ~ a_i > a_j ~ và ~ a_i ~ và ~ a_j ~ đều là số chẵn .

• ~ ∃k: i < k < j ~ và ~ a_k ~ là số lẻ.

Input

• Dòng đầu tiên: chứa số nguyên dương n(~ 1 ≤ n ≤ 10^5 ~) .

• Dòng thứ hai: chứa dãy số ~ a_1, a_2, ..., a_n ~ .

Output

Một số nguyên duy nhất là kết quả bài tin.

Sample

Input #1

5
4 3 2 5 1

Output #1

1

Problem source: Free Contest 55