Drawing

Interview

Time limit1sMemory limit256 MB

Summary
Given n brightness values, decide whether some real a and positive real b make floor(a + b*k) equal every value.
Level

Medium5 of 10

Topics
Math, Brute force, Implementation, Binary search
Solved
No attempts yet

Problem

This semester too many students signed up for Drawing, and the professor in charge can no longer handle them. So each student completes a drawing assignment, scans it, and submits it. Large pictures take too long to grade, so color information is recognized using only brightness, approximated as a natural number between 0 and 255.

The first class was simply about filling a sketchbook by drawing lines, and every student whose brightness exceeded 200 passed.

The second class practices brightness gradation. The assignment is to divide the sketchbook into nn cells and draw lines so that the brightness forms an arithmetic progression. Because the scan approximates it, the passing condition is that for some real number aa and positive real number bb, the brightness of the kk-th cell satisfies ⌊a+bk⌋\lfloor a+bk\rfloor. Here ⌊∙⌋\lfloor\bullet\rfloor means rounding down. You must write the grading program.

That is, given the brightness of nn cells, write a program that decides whether there exist a real number aa and a positive real number bb such that for every natural number kk between 11 and nn, the brightness of the kk-th cell satisfies ⌊a+bk⌋\lfloor a+bk\rfloor.

Input

The first line gives the number of cells nn. nn satisfies 3≤n≤1003\leq n\leq 100.

The second line gives the nn brightness values β1,⋯ ,βn\beta_1,\cdots,\beta_n, separated by spaces. Each brightness satisfies 0≤βi≤2550\leq\beta_i\leq 255.

Output

If the condition holds, print "pass"; otherwise print "fail", without the quotation marks.

Examples2

  1. Example 1

    Input
    4
    1 2 3 5
    Expected output
    pass
  2. Example 2

    Input
    4
    1 2 3 6
    Expected output
    fail