该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

题目描述

在一个神秘的世界，有一个长度为N的数字序列A=[A₁, A₂, ..., A_N]，每个元素A_i的值都是1，2或者3。现在，你的任务是寻找满足条件的下标三元组(i, j, k)，使得1 ≤ i < j < k ≤ N 且 A_i < A_j < A_k。

输入格式

第一行包含一个整数N。

第二行包含N个整数A₁, A₂, ..., A_N (1 ≤ A_i ≤ 3)。

输出格式

一个整数表示答案。

样例

输入

6
1 3 2 1 2 3
    

输出

3
    

数据范围与提示

对于30%的数据，1 ≤ N ≤ 100

对于60%的数据，1 ≤ N ≤ 1000

对于100%的数据，1 ≤ N ≤ 100000

样例