Count Three-Digit Values

Difficulty: 1300 5000 ms 128 MB

prefix-sums

Answer Q range queries: how many elements of a_l..r have exactly three decimal digits (in absolute value)?

Input: the first line has N and Q; the second line has the array; each of the next Q lines has l and r.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values| ≤ 10⁹

Sample Tests

5 2
1 2 3 4 5
1 3
2 5

0
0

1 1
7
1 1

0

Read the Editorial