TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1296
  • 题目
  • P1296上帝的爱好
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    小杉想走进天堂,可却被拦了下来。
    因为上帝很喜欢词这个文体,他要求小杉必须写几首词来应对。
    写的词越多,能带进天堂的刚才拿的礼物就越多。


    我们知道,词都是按照词牌来填的,上帝为了考验小杉,只给了他四种词牌,但只要压韵就算符合词牌。
    小杉已经想好了N个意境优美的句子,每个句子都有一个韵脚。
    符合要求的词的句式应当有如下四种"XXYY","XYXY","XYYX","XXXX",其中X或Y表示韵脚。
    现在小杉想知道,从他想的N个句子之中,最多能按顺序挑选出几首符合条件的词。
    并且词的句子间不能交错,比如你选了1 4 6 8做为一首诗,那么7你就不能再选了。

    输入格式

    第一行有一个数N(N<=4000)。
    第二行有N个不超过10000的正整数,第i个整数表示第i个句子的韵脚,整数相同表示韵脚相同。
    30%的数据N<=100

    输出格式

    对每组测试数据输出一行,仅有一个数字,表示小杉最多能挑出几首词来。

    样例输入

    12
    1 2 4 2 3 1 2 2 1 1 2 2

    样例输出

    2

    提示

    样例最多可以挑出两首词,一种方案如下:
    1 2 4 6/9 10 11 12