You've got an array, consisting of n integers a₁,a₂,...,a_n. Also, you've got m queries, the i-th query is described by two integers l_i,r_i. Numbers l_i,r_i define a subsegment of the original array, that is, the sequence of numbers a_li,a_li+1,a_li+2,...,a_ri. For each query you should check whether the corresponding segment is a ladder.

A ladder is a sequence of integers b₁,b₂,...,b_k, such that it first doesn't decrease, then doesn't increase. In other words, there is such integer x (1≤x≤k), that the following inequation fulfills: b₁≤b₂≤...≤b_x≥b_x+1≥b_x+2...≥b_k. Note that the non-decreasing and the non-increasing sequences are also considered ladders.