Mushroom harvesting II - MarisaOJ: Marisa Online Judge

Marisa needs to pick mushrooms in a forest. The forest can be represented as a straight line with

n

$n$ positions from

1

$1$ to

n

$n$ . At position

i

$i$ in the forest, a type of mushroom

a_{i}

$a_i$ grows. There are

q

$q$ days. On the

i

$i$ -th day, she will stand at position

p_{i}

$p_i$ . She wants to pick mushrooms of types

l_{i}

$l_i$ to

r_{i}

$r_i$ , one of each type if it exists. Instead of moving physically, she can use mushroom-picking magic. If she is standing at position

x

$x$ , she can pick a mushroom at position

y

$y$ at a cost of

| x - y |

$|x - y|$ . For each day, help her calculate the minimum cost to pick the mushrooms. ### Input - The first line contains two integers

n

$n$ and

q

$q$ . - The second line contains

n

$n$ integers

a_{i}

$a_i$ . - The next

q

$q$ lines each contain three integers

p_{i}

$p_i$ ,

l_{i}

$l_i$ , and

r_{i}

$r_i$ . ### Output - For each day, calculate the minimum cost for Marisa to pick the mushrooms. ### Constraints -

1 \leq n, q \leq 2 \times 10^{5}

$1 \leq n, q \leq 2 \times 10^5$ . -

1 \leq l, r, p, a_{i} \leq n

$1 \leq l, r, p, a_i \leq n$ . ### Example Input:

5415313334425313525

$5 4 1 5 3 1 3 3 3 4 4 2 5 3 1 3 5 2 5$

Output:

0313

$0 3 1 3$

### Subtasks -

30

$30\\%$ of the tests have

1 \leq n, q \leq 1000

$1 \leq n, q \leq 1000$ . -

10

$10\\%$ of the tests have

a_{i} = i

$a_i = i$ . -

30

$30\\%$ of the tests have

\forall i l_{i} = 1, r_{i} = n

$\forall i \; l_i=1, r_i=n$ . - The remaining

20

$20\\%$ have no additional constraints.

Topic

Data structure

Rating

2000

Solution (0)

Solution