장바구니 묶음 정리

문제

한 온라인 쇼핑몰의 장바구니에는 상품을 담은 기록이 순서대로 저장된다. 고객이 상품 하나를 담을 때마다 해당 상품 번호가 목록의 맨 뒤에 하나 추가된다. 같은 상품을 여러 번 담으면 같은 번호가 여러 위치에 나타날 수 있다. 이 문제에서는 상품을 취소하거나 수량을 줄이는 기록은 주어지지 않는다. 결제 화면에서는 이 기록을 상품별로 묶어서 보여 주려고 한다. 한 상품에 해당하는 모든 기록을 하나의 행으로 합치고, 그 상품 번호가 전체 기록에 나타난 횟수를 담은 수량으로 표시한다. 상품 번호는 상품을 구별하기 위한 정수이며, 번호의 크기는 화면에 표시할 순서나 상품의 가격과 관계가 없다. 묶은 행의 순서는 각 상품을 처음 담은 순서를 따른다. 서로 다른 두 상품 중 전체 기록에서 먼저 등장한 상품을 위쪽 행에 표시한다. 같은 상품이 나중에 다시 등장해 수량이 늘어나더라도 그 상품의 행을 아래로 옮기지 않는다. 따라서 출력할 상품 번호의 순서는 입력에서 각 번호가 처음 등장한 순서와 같다. 이 쇼핑몰은 같은 상품 세 개마다 한 개의 결제 수량을 빼 주는 행사를 진행한다. 어떤 상품을 c개 담았다면 그 상품의 결제 수량은 c-⌊c/3⌋이다. 이 계산은 상품마다 독립적으로 수행하며, 서로 다른 상품의 남는 수량을 합쳐서 혜택을 적용하지 않는다. 무료로 처리되는 수량도 장바구니에 담은 수량에는 그대로 포함한다. 예를 들어 어떤 상품을 네 개 담았다면 담은 수량은 4이고 결제 수량은 3이다. 결제 수량은 실제 가격이나 금액을 뜻하지 않으며, 이 문제에서는 가격 정보가 주어지지 않는다. 주어진 전체 기록을 읽고, 서로 다른 상품의 개수와 각 행에 표시할 상품 번호, 담은 수량, 결제 수량을 정해진 순서대로 출력하는 프로그램을 작성한다.

입력

첫째 줄에 기록의 개수인 정수 N이 주어진다. 1 ≤ N ≤ 50000이다.
둘째 줄에 상품 번호를 나타내는 N개의 정수 P_i가 기록 순서대로 주어진다. 1 ≤ P_i ≤ 99999이다.

출력

첫째 줄에 서로 다른 상품의 개수 K를 출력한다. 다음 K개 줄에 각 상품의 상품 번호, 담은 수량, 결제 수량을 공백으로 구분하여 출력한다. 행은 해당 상품이 입력에서 처음 등장한 순서대로 출력한다.

8
7 2 7 7 2 9 7 9

3
7 4 3
2 2 2
9 2 2

6
5 5 5 5 5 5

1
5 6 4

4
90 12 61 3

4
90 1 1
12 1 1
61 1 1
3 1 1

출처: Devin.KR 자체 제작