Distinct Elements in Subarrays

Given an array of integers and several queries, each query provides two indices \( l \) and \( r \) (1-indexed). For each query, determine the number of distinct elements in the subarray spanning from \( l \) to \( r \). In other words, for the subarray \( A[l...r] \), compute \( |\{A[l], A[l+1], \dots, A[r]\}| \), where \(|\cdot|\) denotes the cardinality of a set.

This problem is designed to test your understanding of arrays and basic set operations. Efficient handling of queries may be required for larger inputs.

inputFormat

The first line contains two integers \( n \) and \( m \), where \( n \) is the number of elements in the array and \( m \) is the number of queries.

The second line contains \( n \) space-separated integers denoting the array elements.

Each of the next \( m \) lines contains two integers \( l \) and \( r \) (1-indexed), representing a query.

outputFormat

For each query, print a single integer on a new line — the number of distinct elements in the subarray from index \( l \) to \( r \).

5 2
1 2 1 3 2
1 3
2 5

2
3