| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1415
Ohana and Seats Arrangement
Time Limit: 1000ms
Memory Limit: 65536kb Description
Ohana left Tokyo and XiaoGe to live with her granma. In a new place, Ohana is going to make some new friends. As the new semester begins, all the students don't know each other at the beginning.We assume all students sit in a straight line. And we know that two students sit next to each other will become close friends. And every week, teacher will rearrange all the students' seats. And the rules are quite simple: there will be a permutation p, which means this week the person who sits in position x, he will be sits in position p[x] next week. And Ohana wonders how many pairs of friends will there be after an enough time that no new pairs of friends will be created.Please help her. Input
This problem contains multiple tests. The first line there will be a number T which means how many test cases in the final test.Each test consists of two lines. In the first line there will be a numer N, which tells the number of students. In the second line, there will be N numbers indicating the permutation p.1<=N<=2000, p will be a permutation of 1 - N. Output
Output a integer which tells the final number of the pair of friends.
Sample Input
2 2 1 2 6 3 5 1 6 2 4 Sample Output
1 10 Hint
Please note that except the first and the last one, everybody will make two friends.And the same pair of friends should be counted only once.
Source
yuzhou627
|