B"A permutation p of length n is a sequence p_1, p_2, ldots, p_n consisting of n distinct integers, each of which from 1 to n ( 1 <= q p_i <= q n ) . Let's call the subsegment [l,r] of the permutation good if all numbers from the minimum on it to the maximum on this subsegment occur among the numbers p_l, p_{l+1}, ... , p_r . For example, good segments of permutation [1, 3, 2, 5, 4] are: You are given a permutation p_1, p_2, ldots, p_n . You need to answer q queries of the form: find the number of good subsegments of the given segment of permutation. In other words, to answer one query, you need to calculate the number of good subsegments [x ... y] for some given segment [l ... r] , such that l <= q x <= q y <= q r . The first line contains a single integer n ( 1 <= q n <= q 120000 ) -- the number of elements in the permutation. The second line contains n distinct integers p_1, p_2, ldots, p_n separated by spaces ( 1 <= q p_i <= q n ). The third line contains an integer q ( 1 <= q q <= q 120000 ) -- number of queries. The following q lines describe queries, each line contains a pair of integers l , r separated by space ( 1 <= q l <= q r <= q n ). Print a q lines, i -th of them should contain a number of good subsegments of a segment, given in the i -th query. "...