Palindrome list

Problem

A sensor stores readings in a linked list. Print YES if the readings are the same from either end, and NO otherwise. Aim for O(1) extra space.

Example 1

Input

1 2 3 2 1

Output

YES

Example 2

Input

1 2 3 4

Output

NO

Try the problem first. Open one hint at a time.

Hint 1

Find the middle with two pointers.

Hint 2

Reverse the second half, then compare it with the first half.

Write your Python code, run it on the examples and submit it to hidden tests.