07.31

A. Arraytime limit per test1.5 secondsmemory limit per test256 megabytesYou are given an integer arrayaof lengthn.For each indexi, findthe maximum numberof indicesjsuch thatjiand|ai−k||aj−k|, over all possible integer values ofk.InputEach test contains multiple test cases. The first line contains the number of test casest(1≤t≤100). The description of the test cases follows.The first line of each test case contains an integern(1≤n≤5000).The second line containsnintegersa1,a2,…,an(−109≤ai≤109).It is guaranteed that the sum ofnover all test cases does not exceed5000.OutputFor each test case, outputnintegers denoting the answer.ExampleInput6110922105 -10551 2 93 84 272 9 38 4 7 1 6101 9 20 9 829 3 87 1 283 7119 18 29817 283 3 3928 5726 1942 1000000000 -1000000000 19Output01 04 2 2 1 05 4 4 2 2 1 08 4 4 3 5 3 2 2 1 08 7 7 4 5 3 3 2 2 1 0NoteIn the second test, the answers are:Fori=1, you can choosek=−195, thenj=2.Fori=2, you can choosek=5, there exists no indexji.In the third test, the answers are:Fori=1, you can choosek=195, thenj=2,3,4,5.Fori=2, you can choosek=78, thenj=3,4.Fori=3, you can choosek=15, thenj=4,5.Fori=4, you can choosek=15, thenj=5.Fori=5, you can choosek=998244353, there exists no indexji.对每个位置 i，答案 =max(右边比 a[i] 大的个数, 右边比 a[i] 小的个数)#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cint; while(t--) { int n; cinn; vectorinta(n); for(int i=0;in;i++) cina[i]; //在这个数右边比这个数小的数的个数 vectorintlow(n); //在这个数右边比这个数大的数的个数 vectorinthig(n); for(int i=0;in;i++) { //i+1：在这个数右边 for(int j=i+1;jn;j++) { if(a[i]a[j]) hig[i]++; if(a[i]a[j]) low[i]++; } } for(int i=0;in;i++) { int ret=max(hig[i],low[i]); coutret" "; } cout"\n"; } return 0; }B. Beautiful Numberstime limit per test2 secondsmemory limit per test512 megabytes