SP30756 ADANUM - Ada and Numbering

Ada the Ladybug has sequence of different vegetables (for simplicity represented by numbers). She has a few interesting questions of following form: Choose some continuous subsequence of vegetables, then assign each kind of vegetable a distinct positive number. She wants to assign them in a way that the sum (of assigned numbers) over all vegetables will be as low as possible.

The first line contains two integers **1 , the number of vegetables and number of questions.** Next line contains **N** integers **1 , the kinds of vegetables.** Next **Q** lines contains two integers **1 , the left and right indices of Ada's questions.**

For each question answer the minimal possible sum.