A18745.股票购买方案数

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:512MB

题目描述

时间限制:1000ms
内存限制:512MB

今天是 Alex 的生日,他父亲慷慨地送给了他一大笔现金作为生日礼物。然而,Alex 并不满足于仅仅收下这些钱,而是决定将其投入股市,让钱生钱。

为了在股市中获利,Alex 知道必须以较低的价格购入股票,然后以较高的价格售出。给定一只股票在第 ii 天的价格 a[i]a[i],现在他想知道在接下来的 nn 天内,有多少种方法能让他通过购入再售出股票来赚取利润。正式地,你需要找到满足 a[i]<a[j](1i<jn)a[i] < a[j] (1 \le i < j \le n) 的点对个数。

聪明的 Alex 找到了 Macw,但是 Macw 因为学业繁琐未能解答 Alex 的问题,因此 Macw 找到了你,希望聪明的你能帮帮他。

输入格式

输入包含两行,
第一行一个整数 nn,表示给定股票的天数。
第二行包含 nn 个整数,每个整数用空格分隔。第 ii 个整数表示这只股票第 ii 天的单股价格。

输出格式

输出包含一行一个整数,表示 Alex 购入股票再卖出可以赚钱的方法数。

输入输出样例

  • 输入#1

    5
    5 3 1 4 2

    输出#1

    3

说明/提示

样例解释:
三种方案分别为:
Alex可以在第二天买入股票,第四天卖出。
Alex可以在第三天买入股票,第四天卖出。
Alex可以在第三天买入股票,第五天卖出。

数据范围:
对于30%的数据,保证 1n1031 \leq n \leq 10^3
对于100%的数据,保证 1n5×1051 \leq n \leq 5 \times 10^5
对于100%的数据,保证 1a[i]5×1051 \leq a[i] \leq 5 \times 10^5

首页