Triplet Ratio Queries

Given a sequence of integers \(a\) of length \(n\) and \(m\) queries, each query asks to count the number of triplets \((x, y, z)\) such that \(l \le x < y < z \le r\) and the ratio \(a_x : a_y : a_z = 4:2:3\) holds.

A triplet \((x, y, z)\) is valid if there exists an integer \(k\) (possibly zero) such that \(a_x=4k\), \(a_y=2k\), and \(a_z=3k\). All indices are 1-indexed.

inputFormat

The input begins with a single integer \(n\) representing the length of the sequence. The next line contains \(n\) space-separated integers \(a_1, a_2, ..., a_n\). The following line contains a single integer \(m\) denoting the number of queries. Each of the next \(m\) lines contains two integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output a single line with one integer denoting the number of valid triplets in the corresponding subarray.

sample

5
4 2 3 4 2
1
1 3

1