AT_abc439_d [ABC439D] Kadomatsu Subsequence

You are given an integer sequence $ A=(A_1,A_2,\dots,A_N) $ of length $ N $ . Find the number of triples of integers $ (i,j,k) $ that satisfy all of the following: - $ 1 \le i,j,k \le N $ - $ A_i : A_j : A_k = 7:5:3 $ - $ \min(i,j,k) = j $ or $ \max(i,j,k) = j $ .

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Output the answer.

### Sample Explanation 1 The seven triples of integers $ (i,j,k) $ that satisfy the conditions are: - $ (3,9,1) $ - $ A_i : A_j : A_k = 7:5:3 $ , and $ \max(i,j,k) = j $ . - $ (5,9,1) $ - $ A_i : A_j : A_k = 7:5:3 $ , and $ \max(i,j,k) = j $ . - $ (7,9,1) $ - $ A_i : A_j : A_k = 7:5:3 $ , and $ \max(i,j,k) = j $ . - $ (10,2,6) $ - $ A_i : A_j : A_k = 14:10:6 = 7:5:3 $ , and $ \min(i,j,k) = j $ . - $ (10,2,8) $ - $ A_i : A_j : A_k = 14:10:6 = 7:5:3 $ , and $ \min(i,j,k) = j $ . - $ (10,4,6) $ - $ A_i : A_j : A_k = 14:10:6 = 7:5:3 $ , and $ \min(i,j,k) = j $ . - $ (10,4,8) $ - $ A_i : A_j : A_k = 14:10:6 = 7:5:3 $ , and $ \min(i,j,k) = j $ . ### Constraints - All input values are integers. - $ 1 \le N \le 3 \times 10^5 $ - $ 1 \le A_i \le 10^9 $