CF2210F.A Simple Problem

For an array $ b $ of length $ m $ , define $ f(b) $ as follows:

• An array $ c $ of length $ m $ is considered beautiful if and only if for each $ 1 \le i \le m $ , $ c_i $ either equals $ \max(b_1,b_2,\ldots,b_i) $ or $ \min(b_1,b_2,\ldots,b_i) $ . Then, $ f(b) $ is defined as the maximum number of inversions $ ^{\text{∗}} $ over all beautiful arrays.

You are given a permutation $ ^{\text{†}} $ $ p $ of length $ n $ . You need to answer $ q $ queries, where each query contains two integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ). For each query, please compute $ f([p_l,p_{l+1},\ldots,p_{r}]) $ .

$ ^{\text{∗}} $ The number of inversions of an array $ a $ of length $ n $ is defined as the number of pairs of integers $ (i,j) $ such that $ 1 \le i \lt j \le n $ and $ a_i \gt a_j $ .

$ ^{\text{†}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ q $ ( $ 1 \le n,q \le 10^6 $ ), representing the length of $ p $ and the number of queries, respectively.

The second line contains $ n $ distinct integers $ p_1,p_2,\ldots,p_n $ ( $ 1 \le p_i \le n $ ), representing the permutation $ p $ .

Each of the next $ q $ lines contains two integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ), representing a query.

It is guaranteed that the sum of $ n $ and the sum of $ q $ over all test cases both do not exceed $ 10^6 $ .

For each test case, output $ q $ integers, where the $ i $ -th integer represents the answer to the $ i $ -th query.

In the first example test case:

• For the second query, the subarray is $ [1,2] $ . You can take $ c=[\min(1),\min(1,2)]=[1,1] $ , which has $ 0 $ inversions. It can be shown that it is the maximum number of inversions you can get over all beautiful arrays.

In the fourth example test case:

• For the third query, the subarray is $ [3,6,4,9] $ . You can take $ c=[\max(3),\max(3,6),\min(3,6,4),\min(3,6,4,9)]=[3,6,3,3] $ , which will give a total of $ 2 $ inversions. It can be shown that it is the maximum number of inversions you can get over all beautiful arrays.