Problem Statement

Takahashi is practicing dot product calculations in his university linear algebra class.

Given two 7-dimensional vectors \mathbf{a} = (A_1, A_2, \ldots, A_7) and \mathbf{b} = (B_1, B_2, \ldots, B_7), compute their dot product \mathbf{a} \cdot \mathbf{b} = A_1 \times B_1 + A_2 \times B_2 + \cdots + A_7 \times B_7.

Constraints

• -100 \leq A_i \leq 100 (1 \leq i \leq 7)
• -100 \leq B_i \leq 100 (1 \leq i \leq 7)
• All inputs are integers.

Sample Input 1

1 2 3 4 5 6 7
1 1 1 1 1 1 1

Sample Output 1

28

Sample Input 2

3 -1 4 1 -5 9 2
2 7 -1 8 2 -3 6

Sample Output 2

-22

Sample Input 3

100 -100 100 -100 100 -100 100
100 100 -100 -100 100 100 -100

Sample Output 3

-10000

Problem Statement

Takahashi is in charge of a server monitoring system. In this system, N logs arrive in order.

Each log has an integer value representing its "severity level." The severity level of the i-th log (1 \leq i \leq N) to arrive is P_i.

For efficient monitoring, Takahashi has set up his own rule. He checks the logs in order starting from the 1st one, and as soon as he finds a log with a severity level of at least the threshold K, he immediately triggers an alert and goes to respond. Once an alert is triggered, he does not check any subsequent logs.

Determine the number of the log (i.e., which log in the arrival order) that causes Takahashi to trigger an alert. If the severity levels of all N logs are less than K and no alert is ever triggered, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5 50
10 30 55 80 20

Sample Output 1

3

Sample Input 2

4 100
25 50 75 90

Sample Output 2

-1

Sample Input 3

10 1000000000
100 200 300 400 500 600 700 800 900 1000000000

Sample Output 3

10

Problem Statement

Takahashi is creating a match schedule for a sports tournament.

There are N players participating in the tournament, numbered from 1 to N. Each player i (1 \leq i \leq N) is assigned two integers: a "sport number" P_i and a "team number" Q_i. The sport number represents the identifier of the sport the player has entered, and the team number represents the identifier of the team the player belongs to.

In this tournament, player i and player j (1 \leq i < j \leq N) can compete against each other only if they are entered in the same sport and belong to different teams. That is, a match is possible only when P_i = P_j and Q_i \neq Q_j.

Note that there may be multiple players with exactly the same combination of sport number and team number. Such players are considered distinct players distinguished by their player numbers, but since they belong to the same team, they do not satisfy the condition Q_i \neq Q_j and cannot compete against each other.

Find the total number of unordered pairs of players that can compete against each other.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq 10^5
• 1 \leq Q_i \leq 10^5
• All input values are integers
• It is guaranteed that the answer is at most 2^{63} - 1

Sample Input 1

4
1 1
1 2
2 1
1 1

Sample Output 1

2

Sample Input 2

6
1 1
1 2
1 3
2 1
2 1
2 2

Sample Output 2

5

Sample Input 3

10
1 1
1 1
1 2
1 2
1 3
2 1
2 2
2 3
3 1
3 1

Sample Output 3

11

Problem Statement

Takahashi is the manager of a food stall at his university's school festival. He manages N cooking staff members and M cooking tasks.

Each cooking staff member has a "skill level"; the skill level of the i-th staff member is A_i. Similarly, each cooking task has a "required skill level"; the required skill level of the j-th task is B_j.

A staff member can handle a task only if their skill level is at least the required skill level of the task. In other words, the i-th staff member can handle the j-th task only when A_i \geq B_j.

Takahashi assigns staff members to tasks in a one-to-one manner. That is, each staff member can be assigned to at most 1 task, and each task can be assigned to at most 1 staff member. It is not necessary to assign a task to every staff member, and it is acceptable for some tasks to have no staff member assigned to them.

A task to which a staff member is assigned is completed, producing 1 dish as a result. All completed dishes are sold at C yen each. In other words, if K tasks are completed, the total sales amount is K \times C yen.

Find the maximum sales amount Takahashi can obtain when he optimally chooses the assignment of staff members to tasks.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq C \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

3 3 500
5 3 1
2 4 6

Sample Output 1

1000

Sample Input 2

5 4 1000
10 3 7 1 8
5 2 9 4

Sample Output 2

4000

Sample Input 3

7 8 1000000000
100 50 80 30 60 90 10
20 40 60 80 100 55 35 75

Sample Output 3

6000000000

Problem Statement

Takahashi works as a caretaker at a botanical garden. The garden has N flower beds arranged in a straight line, numbered 1, 2, \ldots, N from left to right. Each flower bed i (1 \leq i \leq N) contains a flower of species number P_i. Species numbers are integers between 1 and N inclusive, and different flower beds may contain flowers of the same species number.

The botanical garden has Q tour visits scheduled. The i-th tour (1 \leq i \leq Q) visits the range from flower bed L_i to flower bed R_i (inclusive).

Takahashi wants to know in advance how many distinct types of flowers are in each tour's visiting range, in order to prepare the guide for each tour.

For each tour, determine the number of distinct species numbers contained in the range from flower bed L_i to flower bed R_i.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq P_i \leq N (1 \leq i \leq N)
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
• All inputs are integers

Sample Input 1

5 3
1 2 1 3 2
1 3
2 5
1 5

Sample Output 1

2
3
3

Sample Input 2

10 5
3 1 4 1 5 9 2 6 5 3
1 5
3 7
1 10
5 5
2 8

Sample Output 2

4
5
7
1
6

Sample Input 3

20 8
5 3 5 2 1 4 3 2 1 5 4 3 2 1 5 4 3 2 1 4
1 20
1 1
10 15
5 10
1 10
11 20
7 14
3 8

Sample Output 3

5
1
5
5
5
5
5
5