三元上升子序列

题目描述

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 n 个整数的序列 a_1,a_2,\ldots,a_n 中，三个数被称作thair当且仅当 i 且 a_i。

求一个序列中 thair 的个数。

输入

开始一行一个正整数 n,

以后一行 n 个整数 a_1,a_2,\ldots,a_n。

输出

一行一个整数表示 thair 的个数。

样例

提示

样例2 解释

7 个 thair 分别是：

• 1 2 3
• 1 2 4
• 1 2 3
• 1 2 4
• 1 3 4
• 2 3 4

• 2 3 4

• 对于 100\% 的数据 保证 1 \leq n\le3\times10^4，1\le a_i\leq 10^5。