Gahui the Grappler!!

Interview

Time limit2sMemory limit512 MB

Summary

Given a piecewise linear function through points (i, y_i) with y_0=0, decide whether the ray y=kx meets it anywhere besides the origin.

Level: Medium5 of 10
Topics: Geometry, Math, Implementation, Binary search
Solved: No attempts yet

Problem

This problem is about graphs.

Let $\text{arr\_y}[0] = 0$ and $\text{arr\_y}[i] = y_i$ (where $0 < i \le n$ ). Jo Gahui carried out the following to draw a function $f(x)$ defined on the interval $[0, n]$ .

for(int i=1;i<=n;i++)
    Draw a line segment connecting (i-1,arr[i-1].y) and (i,arr[i].y).

For example, let $n=2$ and $\text{arr\_y}[3] = \{0, 3, 2\}$ .

In this case, the function $f(x)$ is drawn as in the figure above. Jo Gahui wonders whether the functions $y=f(x)$ and $y=kx$ , both defined on the interval $[0, n]$ , meet at any point other than $(0,0)$ . Please satisfy her curiosity.

Input

The first line gives the integer $n$ . The second line gives $n$ numbers. The third line gives $k$ . $1 \le n \le 10^5$ , and every number other than $n$ is an integer greater than or equal to $0$ and less than or equal to $2^{30}$ .

Output

Print T if the two meet at a point other than $(0,0)$ , and F otherwise.

Examples2

Example 1
Input
```
2
3 2
1
```
Expected output
```
T
```
Example 2
Input
```
2
2 3
1
```
Expected output
```
F
```