Good Intervals
InterviewTime limit2sMemory limit128 MB
Given a set S of integers and a target n, count the number of intervals [A,B] with A<B that avoid all elements of S and contain n.
- Level
Medium4 of 10
- Topics
- Math, Array, Implementation
- Solved
- No attempts yet
Problem
You are given a set S of positive integers. For two positive integers A and B, the interval [A, B] is called good if both conditions below hold.
- A < B.
- Every integer x satisfying A <= x <= B is not in S.
Given S and an integer n, count how many good intervals contain n.
Input
The first line contains L, the size of S.
The second line contains the L integers in S, separated by spaces.
The third line contains the integer n.
Output
Output the number of good intervals that contain n.
Constraints
- 1 <= L <= 50
- S contains no duplicate integers.
- Every integer in S is between 1 and 1,000, inclusive.
- 1 <= n <= the largest integer in S.