Lucky Fives

You are given a sequence $a_{1}, a_{2}, \ldots, a_{N}$ of non-negative integers. Your task is to process $Q$ queries of the following format: each query is described by two integers $L \leq R$ and asks to calculate the number of triples $(i, j, k)$, such that $L < i < j < k < R$ and $a_{L} > a_{i} < a_{j} > a_{k} < a_{R}$. ### Input - The first line of the input contains two integers $N$ and $