问题 1910 --单身狗的寻觅

1910: 单身狗的寻觅

时间限制: 1 Sec  内存限制: 128 MB
提交: 68  解决: 17
[提交][状态][讨论版][命题人:]

题目描述

你是个单身狗吗?那就来相亲吧!

西安有一个神奇的地方,叫做“SUST_ACM 婚姻介绍所”

里面有很多需要相亲的程序猿和程序媛。

每个人等待相亲的人都有一个编号(有可能重复),其中程序猿为奇数,程序媛为偶数。

现在他们正排成一排等待相亲。

每个人都只能和相邻的两个人配对,当然绝不允许同性配对。

老大想让介绍所的撮合对数最大化,你告诉老大最多可以匹配多少对吗?

输入

输入包含多组测试数据。

对于每组测试样例:

第一行输入为一个整数 N (1 ≤ N 108)。

第二行输入 N 个正整数(0 < ID  10000)。

输出

输出可以匹配的最大对数。

样例输入

6
1 2 3 4 5 5

样例输出

2

来源

 

[提交][状态]