Competitions

# ADA University - March 7 - Segment Tree

# Interval Less Query

Given an array of size **n**, answer **q** queries of kind: how many numbers on [**l**, **r**] have value less than **x**.

#### Input

The first line contains the size **n** (**1** ≤ **n** ≤ `10`

) of array. The next line contains ^{5}**n** numbers. Number of queries **q** (**1** ≤ **q** ≤ `10`

) is given in the next line. Each of the next ^{5}**q** lines contains one query: three integers **l**, **r** and **x** (**l** ≤ **r**, **1** ≤ **x** ≤ `10`

).^{9}

#### Output

For each query print in a separate line how many numbers on [**l**, **r**] have value less than **x**.

Input example #1

8 1 3 2 4 3 10 5 5 4 1 8 5 1 4 3 5 8 9 2 6 4

Output example #1

5 2 3 3