# Interval Less Query

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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

## Input

The first line contains the size $n(1≤n≤2⋅10_{5})$ of array. The next line contains $n$ integers. Number of queries $q(1≤q≤10_{5})$ is given in the next line. Each of the next $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$.

## Examples

Input #1

Answer #1

Submissions 1K

Acceptance rate 33%