Increasing Median Sequence

Interview

Time limit1sMemory limit1024 MB

Summary

Given three subject scores per exam, decide whether changing at most one score per exam can make the sequence of medians strictly increase.

Level: Medium4 of 10
Topics: Greedy
Solved: No attempts yet

Problem

Gyeonggibuk Science High School gives exams in only three subjects: physics, informatics, and math. Rao, who is about to graduate, wants to write a portfolio based on the $N$ exams he took during school. He does not want his grades to look too low or too high, so for each exam he takes the median of the three subject scores and writes these medians in order in the portfolio.

Rao wants the grades in the portfolio to strictly increase. Equal grades are not allowed. His current report card may not satisfy this, so he asks his friend Jihoon for help. Jihoon can change the score of at most one subject in each exam to any score he wants. Exam scores at Gyeonggibuk Science High School are always non-negative integers, so the changed scores must also be non-negative integers. Write a program that determines whether Rao can make the portfolio he wants.

Input

The first line contains the number of exams $N$ . ( $1 \leq N \leq 200\,000$ )

The second line contains the physics scores $A_1, A_2, \cdots, A_N$ of each exam, separated by spaces, in order. ( $0 \leq A_i \leq 2 \times 10^9$ )

The third line contains the informatics scores $B_1, B_2, \cdots, B_N$ of each exam, separated by spaces, in order. ( $0 \leq B_i \leq 2 \times 10^9$ )

The fourth line contains the math scores $C_1, C_2, \cdots, C_N$ of each exam, separated by spaces, in order. ( $0 \leq C_i \leq 2 \times 10^9$ )

All exam scores are integers.

Output

If an increasing portfolio can be made, print YES. Otherwise, print NO.

Examples2

Example 1
Input
```
3
1 2 3
0 4 3
5 3 3
```
Expected output
```
YES
```
Example 2
Input
```
4
1 2 3 2
0 3 3 2
4 3 5 3
```
Expected output
```
NO
```