1764C. Doremy's City Construction

graphs, greedy, 1400, https://codeforces.com/problemset/problem/1764/C

Doremy's new city is under construction! The city can be regarded as a simple undirected graph with 𝑛 vertices. The 𝑖-th vertex has altitude 𝑎𝑖. Now Doremy is deciding which pairs of vertices should be connected with edges.

Due to economic reasons, there should be no self-loops or multiple edges in the graph.

Due to safety reasons, there should not be pairwise distinct vertices 𝑢, 𝑣, and 𝑤 such that $𝑎_{𝑢} \leq 𝑎_{𝑣} \leq 𝑎_{𝑤}$ and the edges (𝑢,𝑣) and (𝑣,𝑤) exist.

Under these constraints, Doremy would like to know the maximum possible number of edges in the graph. Can you help her?

Note that the constructed graph is allowed to be disconnected.

Input

The input consists of multiple test cases. The first line contains a single integer $t (1 \leq 𝑡 \leq 10^{4})$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n (2 \leq 𝑛 \leq 2 \cdot 10^{5})$ — the number of vertices.

The second line of each test case contains 𝑛 integers $𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑛} (1 \leq 𝑎_{𝑖} \leq 10^{6})$ — the altitudes of each vertex.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed $2 \cdot 10^{5}$ .

Output

For each test case, output the maximum possible number of edges in the graph.

Example

input

4
4
2 2 3 1
6
5 2 3 1 5 2
12
7 2 4 9 1 4 6 3 7 4 2 3
4
1000000 1000000 1000000 1000000

output

Note

In the first test case, there can only be at most 33 edges in the graph. A possible construction is to connect (1,3), (2,3), (3,4). In the picture below the red number above node 𝑖 is 𝑎𝑖.

The following list shows all such 𝑢, 𝑣, 𝑤 that the edges (𝑢,𝑣) and (𝑣,𝑤) exist.

𝑢=1, 𝑣=3, 𝑤=2;
𝑢=1, 𝑣=3, 𝑤=4;
𝑢=2, 𝑣=3, 𝑤=1;
𝑢=2, 𝑣=3, 𝑤=4;
𝑢=4, 𝑣=3, 𝑤=1;
𝑢=4, 𝑣=3, 𝑤=2.

Another possible construction is to connect (1,4), (2,4), (3,4).

An unacceptable construction is to connect (1,3), (2,3), (2,4), (3,4. Because when 𝑢=4, 𝑣=2, 𝑤=3, $𝑎_{𝑢} \leq 𝑎_{𝑣} \leq 𝑎_{𝑤}$ holds, and the respective edges exist.

思路: 要满足条件，先将点权排序，设一个点 i，那么它满足前面的数都小于等于它，后面的数都大于等于它。那么就会有一个贪心方案，以这个点为分段点，后面的所有点与它连边后再与这个点前面的点连边，这样能够满足题目要求，且方案数也越大，但前提是没有与它相等的点。

所以答案就为 $m a x {i \times (n - i)}$ 。

有一点要注意，样例中第 4 个过不去，原因是每个点都与 i 相等，那么方案就是两两相连，答案即为 $⌊ \frac{n}{2} ⌋$

【李石泉-光华-23】就是一个建筑按照高度要么全建向上的路或者向下的路或者同高度的一条路。

python

for i in range(int(input())):
    n = int(input())
    L = sorted(list(map(int, input().split())))
    ans = n//2
    for i in range(1, len(L)):
        if L[i] != L[i-1]:
            ans = max(ans, i*(n-i))
    print(ans)

排序后，从中间位置开始往左一步，往右一步，找第一个与中间值不同的点。

python

t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    altitude = list(map(int, input().split()))
    altitude.sort()

    mid = n//2
    if altitude[0] ==  altitude[-1] == altitude[mid]:
        ans.append(mid)
        continue

    cut = 1
    for i in range(1, (n+1)//2):
        if altitude[mid-i] != altitude[mid]:
            cut = mid - i + 1
            break
        elif altitude[mid+i] != altitude[mid]:
            cut = mid + i
            break
    ans.append(cut*(n-cut))

print('\n'.join(map(str, ans)))

python

# 1764C
t = int(input())
ans = []
for _ in range(t):
    N = int(input())
    a = list(map(int, input().split()))
    a.sort()
    
    mid = N//2
    if a[0] == a[-1] == a[mid]:
        ans.append(mid)
        continue

    b = a[::-1]       # b=sorted(a,reverse=True)
    x = a.index(a[mid])
    y = b.index(a[mid])
    ans.append(max(x*(N-x), y*(N-y)))
    #print(max( x*(N-x), y*(N-y), N//2))
print('\n'.join(map(str, ans)))

1764C. Doremy's City Construction ​

1764C. Doremy's City Construction