You are given an array 𝐴A of length 𝑁N, and a positive integer 𝐾K.It is guaranteed that 1≤𝐴𝑖≤𝐾1≤A i​ ≤K for every index 𝑖i from 11 to 𝑁N.You can do the following at most once:Choose an index 𝑖i (1≤𝑖≤𝑁1≤i≤N) and a value 𝑥x (1≤𝑥≤𝐾1≤x≤K).Then, set 𝐴𝑖:=𝑥A i​ :=x.Find the maximum possible value of the sum of adjacent differences of 𝐴A after performing this operation at most once.That is, maximize the quantity∑𝑖=1𝑁−1∣𝐴𝑖−𝐴𝑖+1∣i=1∑N−1​ ∣A i​ −A i+1​ ∣Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains two space-separated integers 𝑁N and 𝐾K — the length of the array and the maximum allowed integer 𝐾K, respectively.The second line contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1​ ,A 2​ ,…,A N​ , the elements of array 𝐴A.Output FormatFor each test case, output on a new line the answer: the maximum possible sum of adjacent differences of 𝐴A after replacing exactly one element.Constraints1≤𝑇≤1001≤T≤1001≤𝑁≤10001≤N≤10001≤𝐾≤2⋅1061≤K≤2⋅10 6 1≤𝐴𝑖≤𝐾1≤A i​ ≤KThe sum of 𝑁N across all tests won't exceed 10001000.Sample 1:InputOutput32 51 53 87 2 75 2018 3 1 4 1941263Explanation:Test case 11: It's best to leave the array unchanged, giving us a difference of ∣1−5∣=4∣1−5∣=4.Test case 22: It's optimal to set 𝐴2:=1A 2​ :=1, giving us the array [7,1,7][7,1,7]. The sum of adjacent differences is 6+6=126+6=12.Test case 33: It's optimal to set 𝐴3:=20A 3​ :=20, to obtain [18,3,20,4,19][18,3,20,4,19]. The sum of adjacent differences is 6363.

You are given an array 𝐴A containing 𝑁N integers.Consider the following process:Let 𝑆=0S=0 initially.For each 𝑖i from 11 to 𝑁N in order, update 𝑆S to either (𝑆+𝐴𝑖)(S+A i​ ) or (𝑆×𝐴𝑖)(S×A i​ ).That is, either add 𝐴𝑖A i​ to 𝑆S or multiply 𝑆S by 𝐴𝑖A i​ .Before performing the process, you're allowed to freely rearrange the elements of 𝐴A as you like.If you choose the rearrangement of 𝐴A and the sequence of operations optimally, what's the maximum possible value of 𝑆S that you can obtain?This maximum value can be very large, so print it modulo 109+710 9 +7.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains a single integer 𝑁N — the number of elements in the array.The second line contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1​ ,A 2​ ,…,A N​ - the elements of the array.Output FormatFor each test case, output on a new line the maximum possible value of 𝑆S, modulo 109+710 9 +7.Constraints1≤𝑇≤1031≤T≤10 3 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐴𝑖≤1091≤A i​ ≤10 9 The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput244 2 5 231 2 1804Explanation:Test case 11: Choose the rearrangement 𝐴=[2,2,5,4]A=[2,2,5,4]. Then,Add 𝐴1=2A 1​ =2 to 𝑆S. Now, 𝑆=2S=2.Add 𝐴2=2A 2​ =2 to 𝑆S. Now, 𝑆=4S=4.Multiply 𝑆S by 𝐴3=5A 3​ =5. Now, 𝑆=20S=20.Multiply 𝑆S by 𝐴4=4A 4​ =4. Now, 𝑆=80S=80.This is the maximum value that can be obtained.Test case 22: Choose any rearrangement and sum up all the numbers to get 1+1+2=41+1+2=4.This is the maximum value that can be obtained.

You are given an array 𝐴A of length 𝑁N, and an integer 𝐾K.You can perform the following operation:Choose any index 𝑖i (1≤𝑖≤𝑁1≤i≤N), and increase 𝐴𝑖A i​ by 𝐾K.Find the minimum possible value of max⁡(𝐴)−min⁡(𝐴)max(A)−min(A) attainable, if you can perform this operation as many times as you like (possibly, zero times).Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains two space-separated integers 𝑁N and 𝐾K — the length of the array and the parameter 𝐾K.The second line contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1​ ,A 2​ ,…,A N​ — the initial values of the array elements.Output FormatFor each test case, output on a new line the answer: the minimum possible value of max⁡(𝐴)−min⁡(𝐴)max(A)−min(A) if you can perform the given operation any number of times.Constraints1≤𝑇≤1051≤T≤10 5 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐾≤1091≤K≤10 9 1≤𝐴𝑖≤1091≤A i​ ≤10 9 The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput43 41 5 43 212 8 44 11 43 62 8256 121 2 4 128 130 1311008Explanation:Test case 11: Increase the first element by 𝐾=4K=4 to obtain the array [5,5,4][5,5,4].Here, max⁡−min⁡=5−4=1max−min=5−4=1, which is the best possible.Test case 22: The second and third elements can be increased by 22 till they reach 1212, at which point all the elements of the array are equal, so max⁡(𝐴)−min⁡(𝐴)=0max(A)−min(A)=0.Test case 33: Since 𝐾=1K=1, again it's possible to make all the elements equal.Test case 44: Do the following:Increase 𝐴1A 1​ by 1212 repeatedly to make it 133133.Increase 𝐴2A 2​ by 1212 repeatedly to make it 134134.Increase 𝐴3A 3​ by 1212 repeatedly to make it 136136.The array is now [133,134,136,128,130,131][133,134,136,128,130,131].For this array, max⁡(𝐴)−min⁡(𝐴)=136−128=8max(A)−min(A)=136−128=8.It can be shown that this is optimal.

You have been given an array 'A' of N integers. You need to find the maximum value of j - i subjected to the constraint of A[i] <= A[j], where ‘i’ and ‘j’ are the indices of the array.For example :If 'A' = {3, 5, 4, 1}then the output will be 2.Maximum value occurs for the pair (3, 4)Detailed explanation ( Input/output format, Notes, Images )Constraints:1 <= T <= 1001 <= N <= 10 ^ 4-10 ^ 5 <= A[i] <= 10 ^ 5Time limit: 1 sec.Sample Input 1:1934 8 10 3 2 80 30 33 1Sample Output 1:6Explanation:Maximum value occurs for the pair (8, 33)Sample Input 2:1109 2 3 4 5 6 7 8 18 0Sample Output 2:8Explanation:Maximum value occurs for the pair (9, 18)

Initially, we had one array, which was a permutation of size n𝑛 (an array of size n𝑛 where each integer from 11 to n𝑛 appears exactly once).We performed q𝑞 operations. During the i𝑖-th operation, we did the following:choose any array we have with at least 22 elements;split it into two non-empty arrays (prefix and suffix);write two integers li𝑙𝑖 and ri𝑟𝑖, where li𝑙𝑖 is the maximum element in the left part which we get after the split, and ri𝑟𝑖 is the maximum element in the right part;remove the array we've chosen from the pool of arrays we can use, and add the two resulting parts into the pool.For example, suppose the initial array was [6,3,4,1,2,5][6,3,4,1,2,5], and we performed the following operations:choose the array [6,3,4,1,2,5][6,3,4,1,2,5] and split it into [6,3][6,3] and [4,1,2,5][4,1,2,5]. Then we write l1=6𝑙1=6 and r1=5𝑟1=5, and the arrays we have are [6,3][6,3] and [4,1,2,5][4,1,2,5];choose the array [4,1,2,5][4,1,2,5] and split it into [4,1,2][4,1,2] and [5][5]. Then we write l2=4𝑙2=4 and r2=5𝑟2=5, and the arrays we have are [6,3][6,3], [4,1,2][4,1,2] and [5][5];choose the array [4,1,2][4,1,2] and split it into [4][4] and [1,2][1,2]. Then we write l3=4𝑙3=4 and r3=2𝑟3=2, and the arrays we have are [6,3][6,3], [4][4], [1,2][1,2] and [5][5].You are given two integers n𝑛 and q𝑞, and two sequences [l1,l2,…,lq][𝑙1,𝑙2,…,𝑙𝑞] and [r1,r2,…,rq][𝑟1,𝑟2,…,𝑟𝑞]. A permutation of size n𝑛 is called valid if we can perform q𝑞 operations and produce the given sequences [l1,l2,…,lq][𝑙1,𝑙2,…,𝑙𝑞] and [r1,r2,…,rq][𝑟1,𝑟2,…,𝑟𝑞].Calculate the number of valid permutations.InputThe first line contains two integers n𝑛 and q𝑞 (1≤q<n≤3⋅1051≤𝑞<𝑛≤3⋅105).The second line contains q𝑞 integers l1,l2,…,lq𝑙1,𝑙2,…,𝑙𝑞 (1≤li≤n1≤𝑙𝑖≤𝑛).The third line contains q𝑞 integers r1,r2,…,rq𝑟1,𝑟2,…,𝑟𝑞 (1≤ri≤n1≤𝑟𝑖≤𝑛).Additional constraint on the input: there exists at least one permutation which can produce the given sequences [l1,l2,…,lq][𝑙1,𝑙2,…,𝑙𝑞] and [r1,r2,…,rq][𝑟1,𝑟2,…,𝑟𝑞].OutputPrint one integer — the number of valid permutations, taken modulo 998244353998244353.ExamplesinputCopy6 36 4 45 5 2outputCopy30inputCopy10 1109outputCopy1814400inputCopy4 124outputCopy8

Write a program for the maximum possible difference between two subsets of an array.Given an array of n integers. The array may contain repetitive elements, but the highest frequency of any element must not exceed two. Make two subsets such that the difference of the sum of their elements is maximum and both of them jointly contain all elements of the given array along with the most important condition, no subset should contain repetitive elements. ExampleInput:45 8 -1 4Output:Maximum Difference = 18Explanation:Suppose arr[ ] = {5, 8, -1, 4}Let Subset A = {5, 8, 4} & Subset B = {-1}Sum of elements of subset A = 17, of subset B = -1Difference of Sum of Both subsets = 17 - (-1) = 18Input format :The first input line consists of the size of an array, n.The second input consists of the array elements, separated by space.Output format :The output displays the maximum possible difference between two subsets of an array.Refer to the sample output for the formatting specifications.Code constraints :2 ≤ n ≤ 100Sample test cases :Input 1 :74 2 -3 3 -2 -2 8Output 1 :Maximum Difference = 20Input 2 :45 8 -1 4Output 2 :Maximum Difference = 18