#include <iostream>
#include <cstdlib> //calloc()
#include <utility> //pair
#include <algorithm> //min(), max()
using namespace std;
const int capacity = 100; //ёмкость каждого узла списка
template <class T> //T - тип данных, хранящихся в стеке
class stack{
private:
struct node{ //основа стека неограниченной вместительности - односвязный список массивов
node* prev; //указатель на предыдущий узел
T* storage; //массив данных, хранящихся в текущем узле
node(){ //конструктор по умолчанию
prev = nullptr; //список содержит всего один узел
storage = (T*)calloc(capacity+1, sizeof(T)); //выделить память под capacity элементов заданного типа
}
node(node* predecessor){ //параметрический конструктор: добавление нового узла в список
prev = predecessor; //последний узел старого списка будет предшественником нового узла
storage = (T*)calloc(capacity+1, sizeof(T)); //в отличие от malloc, calloc заполняет выделенный участок памяти нулями
}
~node(){ //деструктор
free(storage); //очистить участок памяти, в котором хранится текущий узел
}
};
node* container; //односвязный список
int pos; //текущая позиция указателя. Используется 1-индексация массивов.
int stored; //количество хранимых в данный момент элементов
public:
stack(){ //конструктор по умолчанию
container = new node(); //создать список из одного узла
pos = stored = 0; //0 - служебная позиция, сигнализирующая о том, что стек пуст
}
//(в решении задачи не используется, но объявлять конструктор без деструктора - дурной тон - прим.)
~stack(){ //деструктор
while(container != nullptr){ //пока список не пуст
node* predecessor = container->prev; //сохранить указатель на предшествующий узел
delete container; //очистить текущий узел
container = predecessor; //перейти к предшествующему узлу
}
pos = stored = 0; //сбросить счетчик и указатель на позицию в стеке
}
bool empty(){ //проверка на пустоту
return stored == 0;
}
int size(){ //количество элементов в стеке
return stored;
}
T top(){ //крайний элемент стека
return container->storage[pos];
}
void push(T x){ //добавление элемента
if(pos == capacity){ //если текущий узел заполнен
container = new node(container); //создать новый узел
pos = 0; //и явно указать, что он пуст
}
container->storage[++pos] = x; //добавить элемент в стек
++stored; //количество хранимых элементов увеличилось на 1
}
void pop(){ //удаление элемента
if(pos == 1 && stored >= capacity){ //извлекается последний элемент крайнего узла списка
node* predecessor = container->prev; //сохранить указатель на предыдущий узел
delete container; //очистить память, занимаемую пустым узлом
container = predecessor; //обновить указатель на текущий узел
pos = capacity + 1; //удаление элемента эквивалентно сдвигу указателя влево
//во избежание дублирования участка кода, указателю было присвоено значение
//сдвигом влево которого будет получен указатель на крайний элемент узла
}
--stored; //число хранимых элементов уменьшается на единицу
--pos; //указатель на текущую позицию сдвигается на единицу влево
}
void clear(){ //очистка содержимого стека
while(container != nullptr){ //если список не пуст
node* predecessor = container->prev; //сохранить указатель на предшествующий узел
delete container; //очистить текущий узел
container = predecessor; //перейти к предшествующему узлу
}
container = new node(); //в отличие от деструктора, в списке оставляется один узел
pos = stored = 0; //сброс значений счетчика и указателя на текущую позицию
}
};
//модифицированные стеки: первый элемент пары - хранимое значение, второй - минимум в данной позиции
stack<pair<long long, long long>> head, tail; //голова и хвост очереди
//head - стек, из которого только удаляют элементы
//tail - стек, в который только добавляют элементы
int main(){
int n; cin >> n; //количество операций с очередью
long long a, b, c, x, min_sum = 0;
cin >> a >> b >> c >> x;
while(n--){
x = (a*x*x + b*x + c)/100 % 1000000;
if(x % 5 < 2){ //удалить элемент из очереди
if(head.empty()){ //если соответствующий стек пуст
while(!tail.empty()){ //то перебросить в него содержимое другого стека
long long value = tail.top().first;
tail.pop();
long long minimum = head.empty() ? value : min(head.top().second, value);
head.push({value, minimum});
}
//по окончании обмена принцип FIFO не нарушен, так как элементы
//хвоста очереди расположены в голове в порядке, обратном исходному
}
if(!head.empty()) //если очередь непуста
head.pop(); //удалить первый элемент очереди
}
else{ //добавить элемент в очередь
if(tail.empty()) //если соответствующий стек пуст
tail.push({x, x}); //то добавленный элемент также является текущим минимумом
else //в противном случае
tail.push({x, min(x, tail.top().second)}); //если добавленный элемент меньше всех, содержащихся в стеке
//то обновить текущий минимум
}
if(tail.empty() ^ head.empty()) //если не пуст или первый, или второй стек (но не оба одновременно)
min_sum += tail.empty() ? head.top().second : tail.top().second; //прибавить к сумме доступный минимум
else //если оба стека одновременно либо пусты, либо нет
min_sum += tail.empty() ? 0 : min(tail.top().second, head.top().second); //либо не изменить сумму, либо добавить к ней минимум
//из значений, хранящихся в обоих стеках
}
cout << min_sum << endl; //минимально возможная после всех манипуляций сумма
}
[latex]\scriptsize \begin{pmatrix} 1 & 2 & 3 & 4 & 5 &6 & 7 & 8 & 9 & 10\\ 1 & 5 & 8 & 2 & 4 & 3 &7 & 9 & 6 & 10 \end{pmatrix}[/latex]
