B'In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems. You are given an integer array a[1 ldots n] = [a_1, a_2, ldots, a_n] . Let us consider an empty deque (double-ended queue). A deque is a data structure that supports adding elements to both the beginning and the end. So, if there are elements [3, 4, 4] currently in the deque, adding an element 1 to the beginning will produce the sequence [ color{red}{1}, 3, 4, 4] , and adding the same element to the end will produce [3, 4, 4, color{red}{1}] . The elements of the array are sequentially added to the initially empty deque, starting with a_1 and finishing with a_n . Before adding each element to the deque, you may choose whether to add it to the beginning or to the end. For example, if we consider an array a = [3, 7, 5, 5] , one of the possible sequences of actions looks like this: quad 1.add 3 to the beginning of the deque:deque has a sequence [ color{red}{3}] in it; quad 2.add 7 to the end of the deque:deque has a sequence [3, color{red}{7}] in it; quad 3.add 5 to the end of the deque:deque has a sequence [3, 7, color{red}{5}] in it; quad 4.add 5 to the beginning of the deque:deque has a sequence [ color{red}{5}, 3, 7, 5] in it; Find the minimal possible number of inversions in the deque after the whole array is processed. An inversion in sequence d is a pair of indices (i, j) such that i < j and d_i > d_j . For example, the array d = [5, 3, 7, 5] has exactly two inversions -- (1, 2) and (3, 4) , since d_1 = 5 > 3 = d_2 and d_3 = 7 > 5 = d_4 . The first line contains an integer t ( 1 <= q t <= q 1000 ) -- the number of test cases. The next 2t lines contain descriptions of the test cases. The first line of each test case description contains an intege'...