405745: GYM102058 H Timsort

Python uses a sorting algorithm called Timsort. In short, the algorithm splits the list into mostly sorted subarrays, sorts each subarray using insertion sort, and merges the sorted subarrays. If the list is already mostly sorted, this algorithm runs very quickly.

In this problem, let's focus on the splitting part:

1. Take the longest non-decreasing (a₀ ≤ a₁ ≤ a₂ ≤ ...) or strictly decreasing (a₀ > a₁ > a₂ > ...) subarray that starts from the current index.

2. If the length of the subarray is less than MINRUN, take more elements until the length equals MINRUN or all elements are taken. Let's call these additional elements "bad elements".

If MINRUN is too small, there are too many subarrays to merge; if MINRUN is too large, it takes too much time to apply insertion sort. For this reason, it is important to set an appropriate value of MINRUN. Also, N / MINRUN should be close to a power of 2 to ensure a balanced merging, but we will not consider this in this problem. For each MINRUN value, find the number of subarrays and bad elements.

The first line consists of a single integer N(5 ≤ N ≤ 100, 000), the length of the array. The second line consists of N integers, the elements of the array. The absolute value of each element is at most 10⁹. The third line consists of a single integer Q (1 ≤ Q ≤ 100, 000), the number of queries. Each of the next Q lines contains a single integer MINRUN (2 ≤ MINRUN ≤ N).

For each query, print the number of subarrays and bad elements in one line.

15
2 4 4 3 -1 -2 -2 5 6 5 4 3 2 3 4
3
3
4
5

5 0
4 3
3 5