132. Nth Node From the End

Core1000 ms256 MBSolved by 0%

Build the list, read a value k, and print the value of the kth node counting from the END, where k = 1 is the last node.

If k is larger than the list, print Invalid.

Constraints - `0 ≤ n ≤ 100000` - `1 ≤ k ≤ 200000` - `-1000000 ≤ value ≤ 1000000`

Input

The first line contains an integer n, the number of nodes. The second line contains n space-separated integers — the node values from head to tail. The starter code builds the list for you; work on the nodes, not the array. The third line contains an integer k.

Output

Print one integer — the value of the kth node counting from the end, where k = 1 is the last node, or Invalid if k exceeds the length.

Input5 1 2 3 4 5 2

Output4

Notecounts two back from the end

Input5 1 2 3 4 5 1

Output5

Noteasks for the last node, the smallest valid k

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution