Гра#8695

Гра

3 секунди

64 мегабайти

Легка

Аліса та Боб грають у таку гру:

Їм надано послідовність з $n$ додатних цілих чисел, кожне з яких не перевищує $n$ . Елементи послідовності пронумеровані від $1$ до $n$ . У послідовності можуть бути повторювані числа. На початку гри формується множина $s$ , що містить перші $p$ елементів послідовності. Зверніть увагу, що $s$ може бути мультимножиною, тобто вона може містити однакові елементи. Гравці ходять по черзі, починає Аліса. Кожен хід виконується так:

Гравець, чия черга, вибирає одне число з множини $s$ і забирає його, додаючи його значення до свого рахунку (спочатку рахунок обох гравців дорівнює $0$ ).
Наступне число в послідовності, якщо воно ще є, додається до множини $s$ (якщо послідовність вже порожня, ця дія пропускається). Це означає, що після першого взяття з $s$ , число з індексом $p + 1$ p + 1 додається до множини, після другого - число з індексом $p + 2$ p + 2, і так далі.

Гра триває, поки множина $s$ не стане порожньою. Ми припускаємо, що кожен гравець намагається максимізувати свій рахунок. Результатом гри є різниця між очками, набраними Алісою, та очками, набраними Бобом.

Напишіть програму game, яка повинна обробити $k$ ігор на заданій початковій послідовності.

Вхідні дані

Перший рядок містить два розділені пробілом додатні цілі числа $N$ та $K$ ( $1 \leq N \leq 100000$ 1 \le N \le 100\,000, $1 \leq K \leq 2000$ 1 \le K \le 2\,000, $K \leq N$ K \le N).

Другий рядок складається з $N$ розділених пробілом додатних цілих чисел $a_{1}, a_{2}, \dots, a_{N}$ a_1, a_2, \ldots, a_N, що представляють елементи заданої послідовності ( $1 \leq a_{i} \leq N$ 1 \le a_i \le N для $i = 1, 2, \dots, N$ i = 1, 2, \ldots, N).

Третій рядок містить $K$ розділених пробілом додатних цілих чисел $p_{1}, p_{2}, \dots, p_{K}$ p_1, p_2, \ldots, p_K, кожне з яких визначає початкову множину $S$ , створену з перших $p_{i}$ p_i елементів послідовності для $i$ -ї гри, $i = 1, 2, \dots, K$ i = 1, 2, \ldots, K ( $1 \leq p_{i} \leq N$ 1 \le p_i \le N для $i = 1, 2, \dots, K$ i = 1, 2, \ldots, K).

Вихідні дані

Програма повинна вивести у стандартний вихід $K$ рядків, кожен з яких містить одне ціле число - результат відповідної гри. Рядок номер $i$ повинен містити результат гри номер $i$ (ігри пронумеровані від $1$ до $K$ за вхідними даними).

Приклади

Приклад 1