Rectangular Side Length

Nộp bài
Time limit: 1.0 / Memory limit: 512M

Point: 5

Given three integers ~A, B, C~ are side lengths of a rectangle. Find the length of the remaining side.

Input Specification

  • The first line of input contains an integer ~A~;

  • The second line of input contains an integer ~B~;

  • The third line of input contains an integer ~C~.

  • It is guaranteed that there exists a solution.

Output Specification

  • Output the length of the remaining side.

Examples

Input
3
4
3
Output
4

Constraints

~1 \le A, B, C \le 1000~


Count Perfect Squares

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 5

A perfect square is the result of an integer multiplied by itself. Some examples for perfect squares are ~0, 1, 4, 9, 16, ...~

Given two integers ~A, B~. Find the number of perfect squares between ~A~ and ~B~ (inclusive).

Input Specification

  • Input contains two integers ~A, B~ separated by a whitespace.

Output Specification

  • Output the number of perfect squares between ~A~ and ~B~.

Examples

Input
2 5
Output
1
Explanation

Such integer is: ~4~.


Input
3 25
Output
4
Explanation

Such integers are: ~4, 9, 16, 25~.

Constraints

For all subtasks:
  • ~1\le L\le R\le 10^{12}~

  • ~R-L\le 10^9~

Subtask 1 [40%]
  • ~1\le L\le R\le 10^4~
Subtask 2 [40%]
  • ~1\le L\le R\le 10^8~

  • ~R-L\le 10^5~

Subtask 3 [20%]
  • No additional constraints

Coffee Shop

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 4

TDZ has recently opened a coffee shop.

After using some tricks, he finds out that there will be ~N~ customers visiting the coffee shop on the grand opening day, with the ~i~-th customer coming at minute ~h_i~ (assuming the shop's opening is at minute ~0~). In order to maintain efficiency, he needs to hire some employees.

Each employee can work tirelessly, but he can only serve one customer in one minute. Also, if a customer doesn't receive immediate service, he will leave.

For instance, a customer visits the coffee shop at minute ~5~, then the employee will serve that customer until minute ~6~ and then he will serve other customers (if there is one).

Write a program to help TDZ find the minimum number of employees he needs to hire so that all ~N~ customers that day will be served.

Input Specification

  • The first line of input contains an integer ~N~;

  • The following line of input contains ~N~ integers ~h_1, h_2, ..., h_N~.

Output Specification

  • Output the minimum number of employees needed.

Examples

Input
4
1 10 45 10
Output
2

Constraints

  • ~1\le N\le 10^5~

  • ~1\le h_i\le 10^5~


Cặp số

Nộp bài
Time limit: 1.0 / Memory limit: 512M

Point: 3


Art Exhibition

Nộp bài
Time limit: 1.0 / Memory limit: 512M

Point: 3

There are ~N~ pictures delivered for the exhibition. The ~i~-th painting has a beauty value of ~A_i~.

The exhibition organizer wants to make a triptych by choosing three paintings having indices of ~x, y, z~ such that ~1\le x\lt y\lt z\le N~ and ~A_x = P, A_y = Q, A_z = R~.

Write a program to help the organizer count the number of different triples of paintings that can be made into triptychs. Two triples of paintings are considered different if they do not contain the same set of paintings.

Input Specification

  • The first line of input contains an integer ~N~;

  • The following line of input contains ~N~ integers ~A_1, A_2, ..., A_N~;

  • The third line of input contains three integers ~P, Q, R~.

Output Specification

  • Output the number of distinct triptychs the organizer can make.

Examples

Input
5
1 2 2 1 2
1 2 1
Output
2
Explanation

Such triples of indices of paintings are: ~(1, 2, 4), (1, 3, 4)~.


Input
5
1 2 2 1 2
2 1 1
Output
0
Explanation

There are no ways to make a triptych.

Constraints

For all subtasks:
  • ~3\le N\le 2\times 10^6~

  • ~1\le A_i\le 10^9~

  • ~1\le P, Q, R \le 10^9~

Subtask 1 [30%]
  • ~3\le N\le 200~
Subtask 2 [30%]
  • ~200\lt N\le 3\times 10^4~
Subtask 3 [40%]
  • No additional constraints