Polycarp was given an array a𝑎 of n𝑛 integers. He really likes triples of numbers, so for each j𝑗 (1≤j≤n−21≤𝑗≤𝑛−2) he wrote down a triple of elements [aj,aj+1,aj+2][𝑎𝑗,𝑎𝑗+1,𝑎𝑗+2].Polycarp considers a pair of triples b𝑏 and c𝑐 beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:b1≠c1𝑏1≠𝑐1 and b2=c2𝑏2=𝑐2 and b3=c3𝑏3=𝑐3;b1=c1𝑏1=𝑐1 and b2≠c2𝑏2≠𝑐2 and b3=c3𝑏3=𝑐3;b1=c1𝑏1=𝑐1 and b2=c2𝑏2=𝑐2 and b3≠c3𝑏3≠𝑐3.Find the number of beautiful pairs of triples among the written triples [aj,aj+1,aj+2][𝑎𝑗,𝑎𝑗+1,𝑎𝑗+2].InputThe first line contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases.The first line of each test case contains a single integer n𝑛 (3≤n≤2⋅1053≤𝑛≤2⋅105) — the length of the array a𝑎.The second line of each test case contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (1≤ai≤1061≤𝑎𝑖≤106) — the elements of the array.It is guaranteed that the sum of the values of n𝑛 for all test cases in the test does not exceed 2⋅1052⋅105.OutputFor each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form [aj,aj+1,aj+2][𝑎𝑗,𝑎𝑗+1,𝑎𝑗+2].Note that the answer may not fit into 32-bit data types.

>>polyfit (X, Y, 3) creates and evaluates a polynomial of order 3 where X and Y are arrays of the same length

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

Make PermutationChef has an array 𝐴A of size 𝑁N. He wants to make a permutation†† using this array.Find whether there exists an array 𝐵B consisting of 𝑁N non-negative integers, such that the array 𝐶C constructed as 𝐶𝑖=𝐴𝑖+𝐵𝑖C i​ =A i​ +B i​ is a permutation.†† A permutation of size 𝑁N is an array of 𝑁N distinct elements in the range [1,𝑁][1,N]. For example, [4,2,1,3][4,2,1,3] is a permutation of size 44, while [3,2,2,1][3,2,2,1] and [1,3,4][1,3,4] are not.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of multiple lines of input.The first line of each test case consists of 𝑁N - the size of the array 𝐴AThe next 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 YES if there exists an array 𝐵B such that array 𝐶C constructed as 𝐶𝑖=𝐴𝑖+𝐵𝑖C i​ =A i​ +B i​ is a permutation, otherwise output NO.You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).Constraints1≤𝑇≤1001≤T≤1001≤𝑁≤1001≤N≤1001≤𝐴𝑖≤𝑁1≤A i​ ≤NSample 1:InputOutput454 1 3 2 152 4 3 4 21161 1 1 1 6 6YESNOYESNOExplanation:Test case 11 : Consider 𝐵=[0,4,0,0,0]B=[0,4,0,0,0]. The corresponding array 𝐶C becomes [4,5,3,2,1][4,5,3,2,1], which is a permutation. Some other possible values of 𝐵B for which 𝐶C is a permutation are [1,0,1,1,1][1,0,1,1,1] and [1,3,0,0,0][1,3,0,0,0].Test case 22 : It can be proven that no valid array 𝐵B exists.

For k𝑘 positive integers x1,x2,…,xk𝑥1,𝑥2,…,𝑥𝑘, the value gcd(x1,x2,…,xk)gcd(𝑥1,𝑥2,…,𝑥𝑘) is the greatest common divisor of the integers x1,x2,…,xk𝑥1,𝑥2,…,𝑥𝑘 — the largest integer z𝑧 such that all the integers x1,x2,…,xk𝑥1,𝑥2,…,𝑥𝑘 are divisible by z𝑧.You are given three arrays a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛, b1,b2,…,bn𝑏1,𝑏2,…,𝑏𝑛 and c1,c2,…,cn𝑐1,𝑐2,…,𝑐𝑛 of length n𝑛, containing positive integers.You also have a machine that allows you to swap ai𝑎𝑖 and bi𝑏𝑖 for any i𝑖 (1≤i≤n1≤𝑖≤𝑛). Each swap costs you ci𝑐𝑖 coins.Find the maximum possible value ofgcd(a1,a2,…,an)+gcd(b1,b2,…,bn)gcd(𝑎1,𝑎2,…,𝑎𝑛)+gcd(𝑏1,𝑏2,…,𝑏𝑛)that you can get by paying in total at most d𝑑 coins for swapping some elements. The amount of coins you have changes a lot, so find the answer to this question for each of the q𝑞 possible values d1,d2,…,dq𝑑1,𝑑2,…,𝑑𝑞.InputThere are two integers on the first line — the numbers n𝑛 and q𝑞 (1≤n≤5⋅1051≤𝑛≤5⋅105, 1≤q≤5⋅1051≤𝑞≤5⋅105).On the second line, there are n𝑛 integers — the numbers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (1≤ai≤1081≤𝑎𝑖≤108).On the third line, there are n𝑛 integers — the numbers b1,b2,…,bn𝑏1,𝑏2,…,𝑏𝑛 (1≤bi≤1081≤𝑏𝑖≤108).On the fourth line, there are n𝑛 integers — the numbers c1,c2,…,cn𝑐1,𝑐2,…,𝑐𝑛 (1≤ci≤1091≤𝑐𝑖≤109).On the fifth line, there are q𝑞 integers — the numbers d1,d2,…,dq𝑑1,𝑑2,…,𝑑𝑞 (0≤di≤10150≤𝑑𝑖≤1015).OutputPrint q𝑞 integers — the maximum value you can get for each of the q𝑞 possible values d𝑑.ExamplesinputCopy3 41 2 34 5 61 1 10 1 2 3outputCopy2 3 3 3 inputCopy5 53 4 6 8 48 3 4 9 310 20 30 40 505 55 13 1000 113outputCopy2 7 3 7 7 inputCopy1 13450outputCopy7

Today, Cat and Fox found an array a𝑎 consisting of n𝑛 non-negative integers.Define the loneliness of a𝑎 as the smallest positive integer k𝑘 (1≤k≤n1≤𝑘≤𝑛) such that for any two positive integers i𝑖 and j𝑗 (1≤i,j≤n−k+11≤𝑖,𝑗≤𝑛−𝑘+1), the following holds:ai|ai+1|…|ai+k−1=aj|aj+1|…|aj+k−1,𝑎𝑖|𝑎𝑖+1|…|𝑎𝑖+𝑘−1=𝑎𝑗|𝑎𝑗+1|…|𝑎𝑗+𝑘−1,where x|y𝑥|𝑦 denotes the bitwise OR of x𝑥 and y𝑦. In other words, for every k𝑘 consecutive elements, their bitwise OR should be the same. Note that the loneliness of a𝑎 is well-defined, because for k=n𝑘=𝑛 the condition is satisfied.Cat and Fox want to know how lonely the array a𝑎 is. Help them calculate the loneliness of the found array.InputEach test consists of multiple test cases. The first line contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases. The description of the test cases follows.The first line of each test case contains one integer n𝑛 (1≤n≤1051≤𝑛≤105) — the length of the array a𝑎.The second line of each test case contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (0≤ai<2200≤𝑎𝑖<220) — the elements of the array.It is guaranteed that the sum of n𝑛 over all test cases doesn't exceed 105105.OutputFor each test case, print one integer  — the loneliness of the given array.ExampleinputCopy71032 2 231 0 253 0 1 4 252 0 4 0 270 0 0 0 1 2 480 1 3 2 2 1 0 3outputCopy1134473