Every year for Christmas, Bajtazar decorates his house with a chain made of multicolored light bulbs. This year, Bajtazar chose the colors of the bulbs himself, but he had a hard time deciding, and the chain ended up being a bit too long.

Bajtazar's wife read on a popular website that this year's Christmas fashion requires the chain to contain as many different repetitions as possible. A repetition in the chain is a sequence of two or more consecutive bulbs of the same color. Repetitions are considered different if they consist of a different color of bulbs or have different lengths. For example, the sequence of bulbs 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, where the numbers 1 and 2 denote different colors, contains five different repetitions:

• 1, 1
• 1, 1, 1
• 1, 1, 1, 1
• 2, 2
• 2, 2, 2

Bajtazar intends to shorten his chain by discarding a certain number of initial and/or final bulbs. However, he would like to know how many different repetitions will remain in the chain after such an operation. Our hero is not yet sure exactly how many bulbs he intends to remove, so he could use a library that will help him calculate the requested values for various possible ways of removing bulbs.

Interaction

Your library must provide the following functions:

• inicjuj(n, t) This function will be called only once, at the beginning of the program execution. You can use it to learn the number of bulbs in the chain $n$ and the colors of the consecutive bulbs, given by the vector $t$. The colors of the bulbs are denoted by integers from $0$ to $10^9$. We number them just like the elements of the vector $t$, with numbers from $0$ to $n - 1$.

  • C++: void inicjuj(int n, vector<int> t);

• ile_powtorzen(a, b) Calling this function represents a query for the number of different repetitions in the fragment of the chain from the $a$-th to the $b$-th bulb inclusive ($0 \le a \le b < n$).

  • C++: int ile_powtorzen(int a, int b);

Your program must not read any data (neither from standard input nor from files). It also must not write anything to files or to standard output. It may write to the standard diagnostic output (stderr) – however, remember that this consumes precious time. Do not declare the main function.

Examples

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Let $q$ denote the total number of queries. In all subtasks, $1 \le n \le 250\,000$ and $1 \le q \le 500\,000$.

Note

"Evaluation" tests: 1. $n = 10, q = 5$, bulb colors 1, 1, 2, 2, 3, 3, 4, 4, 5, 5; 2. $n = 5000, q = 5000$, bulb colors 1, 1, 2, 2, 1, 1, 2, 2, . . .; queries satisfy the requirements of subtask 7; 3. $n = 245\,350, q = 500\,000$, one bulb of color 1, two of color 2, three of color 3, . . .

Implementation Details

Example incorrect solutions along with example libraries can be found in the dlazaw folder. The libraries may differ in behavior from those on the graders and may not meet the problem assumptions. They are only intended to show how to interact with the program.

The compilation command looks as follows, assuming the powgrader.cpp file is in the same folder as the solution:

g++ -O3 -static pow.cpp powgrader.cpp -std=c++17

A program compiled in this way reads query data from standard input and writes the results of consecutive ile_powtorzen queries to standard output, on subsequent lines. The input format is as follows:

• line 1: number of queries $z$, including the inicjuj function call;
• line 2: letter i, number $n$, followed by $n$ numbers representing the colors of consecutive bulbs;
• each of the next $z-1$ lines: letter p, followed by numbers $a$ and $b$ describing the ile_powtorzen(a, b) query.