## 「CodeForces 1215E」 Marbles

Monocarp has arranged 𝑛 colored marbles in a row. The color of the 𝑖-th marble is 𝑎𝑖. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color).

In other words, Monocarp wants to rearrange marbles so that, for every color 𝑗, if the leftmost marble of color 𝑗 is 𝑙-th in the row, and the rightmost marble of this color has position 𝑟 in the row, then every marble from 𝑙 to 𝑟 has color 𝑗.

To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.

You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.

## 「CodeForces 1220E」 Tourism

Alex decided to go on a touristic trip over the country.

For simplicity let's assume that the country has 𝑛 cities and 𝑚 bidirectional roads connecting them. Alex lives in city 𝑠 and initially located in it. To compare different cities Alex assigned each city a score 𝑤𝑖 which is as high as interesting city seems to Alex.

## 「CodeForces 1241F」Stack Exterminable Arrays

Let's look at the following process: initially you have an empty stack and an array 𝑠 of the length 𝑙. You are trying to push array elements to the stack in the order 𝑠1,𝑠2,𝑠3,…𝑠𝑙. Moreover, if the stack is empty or the element at the top of this stack is not equal to the current element, then you just push the current element to the top of the stack. Otherwise, you don't push the current element to the stack and, moreover, pop the top element of the stack.

## 「CodeForces 1241D」Sequence Sorting

You are given a sequence 𝑎1,𝑎2,…,𝑎𝑛, consisting of integers.

You can apply the following operation to this sequence: choose some integer 𝑥 and move all elements equal to 𝑥 either to the beginning, or to the end of 𝑎. Note that you have to move all these elements in one direction in one operation.

## 「CodeForces 1241E」Paint the Tree

You are given a weighted tree consisting of 𝑛 vertices. Recall that a tree is a connected graph without cycles. Vertices 𝑢𝑖 and 𝑣𝑖 are connected by an edge with weight 𝑤𝑖.

## 「CodeForces1278D&E」Segment Tree & Tests for problem D

As the name of the task implies, you are asked to do some work with segments and trees.

Recall that a tree is a connected undirected graph such that there is exactly one simple path between every pair of its vertices.

You are given 𝑛 segments [𝑙1,𝑟1],[𝑙2,𝑟2],…,[𝑙𝑛,𝑟𝑛], 𝑙𝑖<𝑟𝑖 for every 𝑖. It is guaranteed that all segments' endpoints are integers, and all endpoints are unique — there is no pair of segments such that they start in the same point, end in the same point or one starts in the same point the other one ends.

## 「CodeForces 1254B」Send Boxes to Alice

This is the harder version of the problem. In this version, 1≤𝑛≤106 and 0≤𝑎𝑖≤106. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems

Christmas is coming, and our protagonist, Bob, is preparing a spectacular present for his long-time best friend Alice. This year, he decides to prepare 𝑛 boxes of chocolate, numbered from 1 to 𝑛. Initially, the 𝑖-th box contains 𝑎𝑖 chocolate pieces.

## 「CodeForces 1277E」 Two Fairs

There are 𝑛 cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from 1 to 𝑛.

Two fairs are currently taking place in Berland — they are held in two different cities 𝑎 and 𝑏 (1≤𝑎,𝑏≤𝑛; 𝑎≠𝑏).