#DS0607. 数对统计 Hard
数对统计 Hard
题目描述
给你 个数字 ,询问共有多少对数字, 到 中没有数字比 或 大。 即对所有位置 , 有 。
输入格式
第一行一个整数 。
接下来一行共 个数。
输出格式
输出1个数,表示答案。
样例解释
符合要求的数对有。
样例解释
符合要求的数对有。
数据规模
对于100%的数据,保证 。
给你 n 个数字 a1,a2,…,an,询问共有多少对数字(i,j)(1≤i<j≤n),ai 到 aj 中没有数字比 ai 或 aj 大。 即对所有位置 k(i<k<j), 有 ak≤min(ai,aj)。
第一行一个整数 n。
接下来一行共 n 个数。
输出1个数,表示答案。
符合要求的数对有(1,2),(2,3),(2,4),(3,4),(4,5)。
符合要求的数对有(1,2),(1,3),(1,6),(1,7),(2,3),(3,4),(3,5),(3,6),(4,5),(5,6),(6,7)。
对于100%的数据,保证 1≤n≤2×105,1≤ai≤109。