Homework Help

Alice was recently given a homework assignment to write a program that would output the number of inversions in any subarray of a given permutation. She happily turned it in and got full marks on her assignment. The next week, their homework assignment was to find the length of the longest increasing subsequences in the same array. Unfortunately, Alice had already thrown away the paper that contained the permutation she needed.

Luckily, this permutation was stored in the program she wrote. Unfortunately, she is now only able to query for the number of inversions in the subarrays of the permutation. As class is close to starting, she asks you for help to solve this problem in a timely manner.

A sequence $a$ is a subsequence of an array $b$ if it is possible to delete some (possibly zero) elements from $b$ to get $a$. A sequence is increasing if every element is strictly greater than all preceding ones, and the LLIS of an array is the length of the longest increasing subsequence.