B"You are given a permutation p_1, p_2, ... , p_n . You should answer q queries. Each query is a pair (l_i, r_i) , and you should calculate f(l_i, r_i) . Let's denote m_{l, r} as the position of the maximum in subsegment p_l, p_{l+1}, ... , p_r . Then f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r) if l <= r or 0 otherwise. The first line contains two integers n and q ( 1 <= n <= 10^6 , 1 <= q <= 10^6 ) -- the size of the permutation p and the number of queries. The second line contains n pairwise distinct integers p_1, p_2, ... , p_n ( 1 <= p_i <= n , p_i neq p_j for i neq j ) -- permutation p . The third line contains q integers l_1, l_2, ... , l_q -- the first parts of the queries. The fourth line contains q integers r_1, r_2, ... , r_q -- the second parts of the queries. It's guaranteed that 1 <= l_i <= r_i <= n for all queries. Print q integers -- the values f(l_i, r_i) for the corresponding queries. Description of the queries: "...