CFCF2176A.Operations with Inversions

普及-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定一个数组 a1,a2,,ana_1, a_2, \ldots, a_n。每次操作,你可以选择一对下标 i,ji, j,满足 1i<jn1 \le i < j \le nai>aja_i > a_j,并且从数组中删除下标为 jj 的元素。操作后,数组的大小减少 11,元素的相对顺序不变。

请你判断,在最优策略下,最多可以进行多少次这样的操作。

输入格式

每个测试包含多个测试用例。第一行为测试用例的数目 tt1t501 \le t \le 50)。接下来是测试用例的描述。

每个测试用例的第一行为一个整数 nn1n1001 \le n \le 100)——数组的初始长度。

每个测试用例的第二行为 nn 个自然数 a1,a2,,ana_1, a_2, \ldots, a_n1ain1 \le a_i \le n)。

输出格式

对于每个测试用例,输出在给定数组上最多能够进行的操作次数。

输入输出样例

  • 输入#1

    5
    3
    3 2 1
    3
    1 2 3
    3
    3 3 3
    5
    3 1 4 5 2
    1
    1

    输出#1

    2
    0
    0
    2
    0

说明/提示

在第一个样例中,可以首先选择下标为 i=2,j=3i = 2, j = 3 的一对,值分别为 a2=2,a3=1a_2 = 2, a_3 = 1,并删除 a3a_3。此时数组变为 a=[3,2]a = [3, 2]。之后可以通过选择 i=1,j=2i = 1, j = 2 再次删除第二个元素。操作总次数为 22

在第二、第三和第五个样例中,无法进行任何操作,因为没有符合条件的下标对。

在第四个样例中,可以删除第二个和第五个元素。可以证明,这就是最优答案,不存在能够删除更多元素的方案。

首页