企业官网建设流程全解析

A. Array

time limit per test

1.5 seconds

memory limit per test

256 megabytes

You are given an integer array a of length n.

For each index i, find the maximum number of indices j such that j>i and |ai−k|>|aj−k|, over all possible integer values of k.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤5000).

The second line contains n integers a1,a2,…,an (−109≤ai≤109).

It is guaranteed that the sum of n over all test cases does not exceed 5000.

Output

For each test case, output n integers denoting the answer.

Example

Input

6

1

1092

2

105 -105

5

1 2 93 84 2

7

2 9 38 4 7 1 6

10

1 9 20 9 829 3 87 1 283 7

11

9 18 29817 283 3 3928 5726 1942 1000000000 -1000000000 19

Output

0

1 0

4 2 2 1 0

5 4 4 2 2 1 0

8 4 4 3 5 3 2 2 1 0

8 7 7 4 5 3 3 2 2 1 0

Note

In the second test, the answers are:

• For i=1, you can choose k=−195, then j=2.
• For i=2, you can choose k=5, there exists no index j>i.

In the third test, the answers are:

• For i=1, you can choose k=195, then j=2,3,4,5.
• For i=2, you can choose k=78, then j=3,4.
• For i=3, you can choose k=15, then j=4,5.
• For i=4, you can choose k=15, then j=5.
• For i=5, you can choose k=998244353, there exists no index j>i.

对每个位置 i，答案 =max(右边比 a[i] 大的个数, 右边比 a[i] 小的个数)

#include<iostream> #include<vector> #include<algorithm> #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin>>t; while(t--) { int n; cin>>n; vector<int>a(n); for(int i=0;i<n;i++) cin>>a[i]; //在这个数右边比这个数小的数的个数 vector<int>low(n); //在这个数右边比这个数大的数的个数 vector<int>hig(n); for(int i=0;i<n;i++) { //i+1：在这个数右边 for(int j=i+1;j<n;j++) { if(a[i]<a[j]) hig[i]++; if(a[i]>a[j]) low[i]++; } } for(int i=0;i<n;i++) { int ret=max(hig[i],low[i]); cout<<ret<<" "; } cout<<"\n"; } return 0; }

B. Beautiful Numbers

time limit per test

2 seconds

memory limit per test

512 megabytes