Algorithm Tutoring

Time limit2sMemory limit1024 MB

Summary

Each student i accepts partners j with l_i <= |i-j| <= r_i; find the maximum |a_i - a_j| over mutually compatible pairs, or -1.

Level: Medium7 of 10
Topics: Segment tree, Sorting, Array, Binary search
Solved: No attempts yet

Problem

The algorithm academy run by Jihwan has $N$ students, numbered $1$ through $N$ .

The academy uses a rating system to represent each student's skill level. Every student has a rating, and the rating of student $i$ is denoted $a_i$ .

To raise his students' ratings, Jihwan wants to pick $2$ students and secretly tutor them. However, a student dislikes others whose number differs from theirs by too much or too little. So student $i$ is only willing to be tutored together with students whose number differs from $i$ by at least $l_i$ and at most $r_i$ .

Find the maximum possible rating difference when choosing $2$ students that satisfy the above conditions.

Input

The first line gives the number of students in the algorithm academy, $N$ . ( $2 \le N \le 200\,000$ )

Lines $2$ through $N+1$ give information about the students. Line $i+1$ contains three integers $a_i$ , $l_i$ , $r_i$ separated by spaces, meaning that student $i$ has rating $a_i$ and is only willing to be tutored together with students whose number differs from $i$ by at least $l_i$ and at most $r_i$ . ( $1 \le a_i \le 10^9$ , $1 \le l_i \le r_i \le N$ )

Output

Print the maximum rating difference over all choices of $2$ students that satisfy every condition in the problem.

If no such pair of students exists, print $-1$ .

Examples3

Example 1
Input
```
4
1 1 4
2 1 1
3 1 2
7 1 2
```
Expected output
```
4
```
Example 2
Input
```
5
10 1 1
3 1 1
2 1 3
3 1 1
9 2 4
```
Expected output
```
7
```
Example 3
Input
```
3
5 1 1
2 2 3
3 1 1
```
Expected output
```
-1
```