题目描述

给定一个长度为 $n$ 的双向链表，以及一个目标值 $x$。请你从链表的头节点开始向尾部遍历，查找链表中首次出现值为 $x$ 的节点，并输出该节点的正向序号。

• 节点序号从头节点开始算起，编号为 $1, 2, 3, \dots, n$。
• 如果整个双向链表中都不存在值为 $x$ 的节点，请输出 -1。

输入格式

第一行包含一个整数 $n$ $(1 \le n \le 10^5)$，表示双向链表的长度。 第二行包含 $n$ 个整数，表示双向链表从头到尾各个节点的值。整数之间用空格隔开。 第三行包含一个整数 $x$ $(-10^9 \le x \le 10^9)$，表示要查找的目标值。

输出格式

输出一行一个整数，表示值为 $x$ 的节点首次出现的序号；若不存在则输出 -1。

样例输入 1

6
7 3 9 3 5 2
3

样例输出 1

2

样例说明 1

目标值为 3，在链表中第 2 个节点和第 4 个节点的值均为 3，首次出现是在第 2 个位置，因此输出 2。

样例输入 2

5
1 2 3 4 5
10

样例输出 2

-1

样例说明 2

链表中不存在值为 10 的节点，输出 -1。