TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1012
  • 题目
  • P1012波浪数列
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    设数列{an}中至少有3个数,将{an}中相邻的两个数依次作差(前面的减后面的),得到一个新的数列{bn},即b[i]=a[i+1]-a[i],如果数列{bn}满足b[i]*b[i+1]<0(1<=i<=n-1),即{bn}中任意两个相邻的数之积小于0,则称数列{an}为一个波浪数列。现在给出一个数列,从这个数列中去掉一些数,使剩下的数构成一个波浪数列,求最少要去掉的个数。

    输入格式

    第一行一个正整数n,接下来n行,每行一个整数,范围在int以内。

    输出格式

    一个整数,表示需要去掉的最少个数;如果无论去掉多少个都不能变成波浪数列,输出“not exists”(不包含引号)。

    样例输入

    10
    734
    9025
    465
    10
    16459
    87
    14
    8102
    7590
    175

    样例输出

    3

    提示

    注意:对于50%的数据,3<=n<=5000;
    对于100%的数据,3<=n<=100000。


    来源  cqnk 2005级 命题:Cauchy;审题:Chyy;数据:Chyy。